10771077 SUSTech Online Judge
Problem 1077 --Minimum Bridge Cost

1077: Minimum Bridge Cost

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 1351  Solved: 314
[Submit][Status][Web Board]

Description

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.

Input

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.

Output

For each test cast, print the minimum cost or -1.

Sample Input

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

Sample Output

7

HINT


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.

Source

[Submit][Status]