F. 【入门】重建电路

    Type: Default 1000ms 32MiB

【入门】重建电路

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

说明

小A同学所在的城市遭受了洪灾,城市中的电路受到了严重的破坏。政府部门一方面要救灾,一方面要用最小的代价来重建电路系统。

现在已知该城市有若干个村庄(编号为0~n-1),并已知村庄之间如果重建电路所需要的花费,请你编程帮助该城市计算出,如果要使得该城市恢复电路系统,最少的花费是多少?请注意:只需要保证任意两个村庄之间至少存在一条通路,电路系统即可恢复。

输入格式

输入的第一行为一个整数T(1<=T<=50),表示有T组测试数据。

每组输入第一行是两个正整数N,E(2<=N<=500,N<=E<=N*(N-1)/2),分别表示该城市村庄个数和原有电力线路的个数。

接下来的E行,每行包含三个整数A,B,K(0<=A,B<N,0<=K<1000)。A和B分别表示电力线路的起始村庄代号。如果K=0,表示这条线路仍然正常。如果K是一个正整数,表示这条线路需要花费K的代价来重建。
题目保证输入中没有重边,也没有起始村庄相同的边。本题的数据确保一定能重建电路系统。

输出格式

对于每组输入,输出重建电力系统所需的最小花费,以此来保证任意两个村庄之间至少存在一条通路。

样例

1
3 3
0 1 5
0 2 0
1 2 9
5

第七届SWPU-ACM老生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
187
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
45