#include<stdio.h> #include<algorithm> using namespace std; struct vi { int start; int end; int cost; }edge[130000],et; int p[500]; int Find(int n) { return n==p[n]?n:p[n]=Find(p[n]); } bool cmp(vi a,vi b) { return a.cost<b.cost; } int main() { int t,n,e,i,k,sum,ST,EN; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&e); for(i=0;i<n;i++) p[i]=i; for(k=i=0;i<e;i++) { scanf("%d%d%d",&et.start,&et.end,&et.cost); if(et.cost==0) p[Find(et.start)]=Find(et.end); else edge[k++]=et; } sort(edge,edge+k,cmp); for(sum=i=0;i<k;i++) { ST=Find(edge[i].start); EN=Find(edge[i].end); if(ST!=EN) { p[ST]=EN; sum+=edge[i].cost; } } printf("%d\n",sum); } return 0; } /************************************************************** Problem: 2069 User: admin Language: C++ Result: Accepted Time:54 ms Memory:2672 kb ****************************************************************/