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.
1
5 5 2
1 2 1
1 3 6
3 4 1
1 4 5
2 4 4
2 5 3
4 5 2
7
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.