Minimum Magical Cost to Connect Towns

You are given multiple test cases. For each test case, you are given a connected undirected weighted graph representing towns connected by magical paths. The graph consists of N towns (numbered from 1 to N) and M magical paths. Each magical path is described by three integers: u, v and w, indicating that there is an undirected path between town u and town v with magical cost w.

Your task is to compute the minimum total magical cost required to connect all the towns. In other words, you need to find the cost of a minimum spanning tree (MST) of the graph. Recall, a spanning tree of a graph with N nodes has exactly $N-1$ edges. If it is not possible to connect all towns (i.e. a spanning tree does not exist), output -1.

Note: Use the standard input and output. If there are multiple test cases, process each test case independently and output the result on a new line.

inputFormat

The first line of input contains an integer T denoting the number of test cases.

For each test case, the first line contains two integers N and M where N is the number of towns and M is the number of magical paths. The next M lines each contain three integers u, v and w representing a magical path between towns u and v with cost w.

outputFormat

For each test case, output a single integer, which is the minimum total magical cost to connect all towns. If it is not possible to connect all towns, output -1. Each answer should be printed on a new line.

## sample

2
4 5
1 2 4
1 3 3
2 3 2
2 4 7
3 4 1
3 3
1 2 5
2 3 10
1 3 8

6
13

</p>