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

Description

给定n(n<=500)个顶点,以及E(E<=20000)条边,计算最小生成树的权值.

Input

第一行输入T表示有T组数据。每组数据第一行输入n、E,分别表示顶点数和边数. 接下来
输入E行每行三个正整数u(1<=u<=n)、v(1<=v<=n)、w,表示顶点u到顶点v之间无向边
长度w(可能有重边)。

Output

输出T行正整数,第i行表示第i组数据的最小生成树权值, 若不能构建最小生成树输出-1。

Sample Input

3
2 2
1 2 1
1 2 2
3 1
2 3 1
3 3
1 2 2
1 2 3
2 3 1

Sample Output

1
-1
3
Submit Your Code                        Discuss



苏ICP备2022026913号-1