Minimum Cost to Connect All Departments

You are given several departments and a list of possible cable connections between them. Each cable connection connects two departments and has an associated cost. Your goal is to connect all departments with the minimum total cost using Kruskal's algorithm (i.e. computing the Minimum Spanning Tree, MST). If it is impossible to connect all departments, output -1.

Note: Departments are numbered from 1 to N. For each test case, you will be provided with the number of departments N and the number of available cable connections M, followed by M lines each containing three integers: u, v and w, where u and v are the departments connected by the cable and w is the cost of that connection.

The solution must read input from standard input (stdin) and output the result to standard output (stdout). For each test case, print the minimum total cost on a new line. If not all departments can be connected, print -1 for that test case.

The formula for the problem can be summarized as follows:

$$MSTCost = \begin{cases} \text{Sum of weights in the MST,} & \text{if MST exists} \\ -1, & \text{otherwise} \end{cases} $$

inputFormat

The first line contains an integer T (1 ≤ T ≤ 100), representing the number of test cases. For each test case, the first line contains two integers N (number of departments) and M (number of cable connections). Each of the following M lines contains three integers u, v and w where:

• 1 ≤ u, v ≤ N
• u ≠ v
• 1 ≤ w ≤ 10⁶

Departments are numbered from 1 to N.

outputFormat

For each test case, output a single line containing the minimum total cost to connect all departments. If it is impossible to connect all departments, print -1.

## sample

4
4 5
1 2 1
1 3 4
1 4 3
2 3 2
3 4 5
3 3
1 2 3
2 3 1
1 3 1
4 2
1 2 1
3 4 1
2 1
1 2 3

6
2
-1
3

</p>