题目

京海市城市规划部门计划修建一个大型地铁网络，将城市中的重要交通支点用地铁网络连接起来，以方便市民通行。 但是节点过多，预算不够，让京海市城市规划部门十分头疼，请你用计算机帮助他们进行设计这个网络，要求是在将重要交通支点连接起来的前提下，使修建地铁网络的费用最低。

Input

存在多组测试数据，每组数据包含所给定的地图要素信息：

每组数据的第一行包含两个整数：重要交通节点的数量 N 和可修建地铁路线的数量 M 。 重要交通节点的编号用 1 到 N 的整数代替。

之后的 M 行包含三个整数：前两个整数为地铁线路连接的两个节点的编号 a 和 b ，第三个整数为通过该线路连接这两个节点的花费 W 。

1≤N≤50
1≤M≤10^5
1≤W≤100

注意！！！若 N 为 0 ，则结束输入。

Output

对于每组测试数据，仅输出一行，包含一个整数：将所有关键节点连接起来的最低花费。 保证一定至少有一种方案，使得所有关键节点连通。

Sample

input:

1 0

2 3
1 2 37
2 1 17
1 2 68

3 7
1 2 19
2 3 11
3 1 7
1 3 5
2 3 89
3 1 91
1 2 32

5 7
1 2 5
2 3 7
2 4 8
4 5 11
3 5 10
1 5 6
4 2 12

0

output:

0
17
16
26

代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100010

int n, m; //n个点，m条边
int sum, ans, cnt; //sum记录连接的边数
int fa[MAXN];
struct node { //结构体
   int x;//端点之一
   int y;//端点之二
   int w;//边权值
} a[MAXN];
int cmp(node x, node y) { //将数据按照从小到大的顺序排序
   return x.w < y.w;
}
int find(int x) {
   if (x == fa[x])
   	return x;
   else {
   	fa[x] = find(fa[x]);
   	return fa[x];
   }
}
void kruskal() {
   for (int i = 1; i <= m; i++) {
   	cin >> a[i].x >> a[i].y >> a[i].w;
   }
   for (int i = 1; i <= n; i++) {
   	fa[i] = i;
   }
   sort(a + 1, a + 1 + m, cmp);
   for (int i = 1; i <= m; i++) { //加边
   	int x = find(a[i].x);
   	int y = find(a[i].y);
   	if (x != y) { //如果不在同一个集合
   		fa[y] = x; //合并
   		sum++;//边数加1
   		ans += a[i].w;
   		if (sum == n - 1) { //如果边数达到n-1，则寻找完毕
   			break;
   		}
   	}
   }
}

int main() {
   while (cin >> n) {
   	if (n == 0) break;
   	ans = 0;
   	sum = 0;
   	cin >> m;
   	kruskal();
   	cout << ans << endl;
   }

   return 0;
}