最小生成树
Time Limit: 2000 MSMemory Limit: 1000 KB

Description

给出一个无向网,求该无向网的最小生成树。各条边的权重不超过100000。

Input

输入的第一行是一个int型整数T,表示一个有T组数据。
每组数据第一行包含两个数n,m。n表示该网的顶点个数,3 ≤ N ≤ 100,m 表示无向边的个数。
接下来有m行,每行三个数,ai,bi,ci,表示点ai到点bi有一条权重为ci的边。

Output

输出该最小生成树的权重。保证最小生成树存在。

Sample Input

1
4 5
1 2 4
1 3 9
2 3 8
4 3 16
2 4 17

Sample Output

28
Submit Your Code                        Discuss



苏ICP备2022026913号-1