UOJ Logo PP Online Judge

PPOJ

#117. 数据结构实验4-1: 最小生成树

统计

描述

用克鲁斯卡尔(Kruskal)算法求无向网的最小生成树。

输入

输入数据第一行为两个正整数 $n <= 10000$ 和 $m$,分别表示顶点数和边数。后面紧跟 $m$ 行数据, 每行数据是一条边的信息,包括三个数字,分别表示该边的两个顶点和边上的权值。 保证形成稀疏图。

输出

边权值顺序输出 Kruskal 算法求得的最小生成树的边集,每行一条边,包括三个数字,分别是该边的两个顶点和边上的权值,其中第一个顶点的编号应小于第二个顶点的编号。

样例一

输入

8 11 
1 2 3 
1 4 5 
1 6 18 
2 4 7 
2 5 6 
3 5 10 
3 8 20 
4 6 15 
4 7 11 
5 7 8 
5 8 12

输出

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