1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4  5 #define MAXN 10005 6 #define INF  0xffffff 7  8 typedef struct { 9     int c, s, e;10 } edge_st;11 12 edge_st edges[100005];13 int pre[MAXN];14 int deg[MAXN];15 int n, m, ans;16 17 int comp(const void *a, const void *b) {18     return ((edge_st *)b)->c - ((edge_st *)a)->c;19 }20 21 int find(int x) {22     return x==pre[x] ? x:pre[x]=find(pre[x]);23 }24 25 void merge(int i) {26     int a, b;27 28     a = find(edges[i].s);29     b = find(edges[i].e);30     if (a != b) {31         if (deg[a] == 0) {32             pre[a] = b;33             ans += edges[i].c;34         } else if (deg[b] == 0) {35             pre[b] = a;36             ans += edges[i].c;37         }38     } else {39         if (deg[a] == 0) {40             ++deg[a];41             ans += edges[i].c;42         }43     }44 }45 46 int main() {47     int i;48 49     while (scanf("%d %d", &n, &m)!=EOF && (n||m)) {50         for (i=0; i<m; ++i)51             scanf("%d %d %d", &edges[i].s, &edges[i].e, &edges[i].c);52         qsort(edges, m, sizeof(edge_st), comp);53         for (i=0; i<n; ++i)54             pre[i] = i;55         memset(deg, 0, sizeof(deg));56         ans = 0;57         for (i=0; i<m; ++i)58             merge(i);59         printf("%d\n", ans);60     }61 62     return 0;63 }