There are n buildings in school. The
president wants you to connect all these buildings by making some
bridges among them. The construction should follow these requirements: (i) all buildings are connected, (ii) total cost
is minimized.
There are total m + K bridges you can choose. If you cannot make all buildings connected by these m+K
bridges, print -1, otherwise, print the minimized total cost.
Note: The total cost is the cost of the remaining bridges after you insert.
The first line will be an integer T. (1
<= T <= 50) T is the number of test case.
For each test case, the first line will be
three integers n, m and K.(n <= 5000, m, K <= 10000) Then there will be m
+ K lines. Each line will be three integers x y w, meaning we can build a bridge
between island x and island y with w cost. (1 <= x, y <= n, w <= 104)
The islands are labeled from 1 to n.
For each test cast, print the minimum cost
or -1.
For the first sample, we remove the bridges
between 1 3, 2 4, 1 4; add bridges 2 5, 4 5. The total cost is 1 + 3 + 2 + 1 =
7. 7 is the minimum cost we need.