#include #include #include using namespace std; int n,m,k; int a[1<<17],b[1<<17],c[1<<17]; long sum; #include struct UF{ int n; vectorparent,rank; UF(int n_=0):n(n_),parent(n_),rank(n_,0) { for(int i=0;i>n>>m>>k; vector > >G; for(int i=0;i>a[i]>>b[i]>>c[i]; sum+=c[i]; G.push_back(make_pair(c[i],make_pair(a[i],b[i]))); } UF uf(n+1); for(int i=0;i>e; e--; sum-=c[e]; uf.unite(a[e],b[e]); } sort(G.begin(),G.end()); for(int i=0;i