某个局域网内有 nn 台计算机和 kk 条 双向 网线，计算机的编号是 1∼n1∼n。由于搭建局域网时工作人员的疏忽，现在局域网内的连接形成了回路，我们知道如果局域网形成回路那么数据将不停的在回路内传输，造成网络卡的现象。
注意：
- 对于某一个连接，虽然它是双向的，但我们不将其当做回路。本题中所描述的回路至少要包含两条不同的连接。
- 两台计算机之间最多只会存在一条连接。
- 不存在一条连接，它所连接的两端是同一台计算机。
因为连接计算机的网线本身不同，所以有一些连线不是很畅通，我们用 f(i,j)f(i,j) 表示 i,ji,j 之间连接的畅通程度，f(i,j)f(i,j) 值越小表示 i,ji,j 之间连接越通畅。
现在我们需要解决回路问题，我们将除去一些连线，使得网络中没有回路且不影响连通性（即如果之前某两个点是连通的，去完之后也必须是连通的），并且被除去网线的 Σf(i,j)Σf(i,j) 最大，请求出这个最大值。
去除的最大就代表剩下的最小，而且还得连通，明显是最小生成树，无自环，无重边，这个没有回路怎么理解呢？就是没有环吧，好像最小生成树本来就没有环吧哈哈。看了一眼稀疏图，直接上kruskal，虽然这数据比较水，用prim和kruskal都可以过，但还是用最好的吧。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define inf 0x3f3f3f3f3f3f3f3f
#define endl "\n"
#define lowbit(x) (x&(-x))
const int N = 110;
int fa[N];
struct E{
int a,b,w;
bool operator < (const E& tmp){
return this->w < tmp.w;
}
}edg[N];
int n,k,sum1,sum2;
int find(int x){
if(x==fa[x]) return x;
else{
fa[x] = find(fa[x]);
return fa[x];
}
}
void kul(){
for(int i = 1; i <= k; i++){
int pa = find(edg[i].a), pb = find(edg[i].b);
if(pa!=pb){
sum2 += edg[i].w;
fa[pa] = pb;
}
}
}
void solve(){
cin >> n >> k;
for(int i = 1; i <= n; i++) fa[i] = i;
for(int i = 1; i <= k; i++){
cin >> edg[i].a >> edg[i].b >> edg[i].w;
sum1 += edg[i].w;
}
sort(edg+1,edg+1+n);
kul();
cout << sum1-sum2 << endl;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T=1;
//cin >> T;
while(T--) solve();
return 0;
}
//
//
//
//
//