Python 最小生成树

欧德奈瑞

7-1 村村相连
漳州市政府调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。市政府的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。

输入格式:
测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N(N<100)和两村庄间的公路数M；随后的M行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N、M为0时，输入结束，该用例不被处理。

输出格式:
对每个测试用例，在1行里输出最小的公路总长度，如果未能找到请输出"no found!"。

输入样例1:
在这里给出两组输入。例如：

1. 3 3
   
2. 1 2 10
   
3. 1 3 20
   
4. 2 3 40
   
5. 4 6
   
6. 1 2 10
   
7. 1 3 40
   
8. 1 4 10
   
9. 2 3 30
   
10. 2 4 20
    
11. 3 4 50
    
12. 0 0

复制代码

输出样例1:
在这里给出相应的输出。例如：

1. 30
   
2. 50

复制代码

输入样例2:
在这里给出两组输入。例如：

1. 4 5
   
2. 1 2 10
   
3. 1 3 40
   
4. 1 4 10
   
5. 2 4 20
   
6. 3 4 50
   
7. 5 6
   
8. 1 2 20
   
9. 1 3 10
   
10. 1 4 20
    
11. 1 5 10
    
12. 2 5 30
    
13. 4 5 30
    
14. 0 0

复制代码

输出样例2:
在这里给出相应的输出。例如：

1. 60
   
2. 60

复制代码