#1595 Time Travelling Salesman

43  1 s   128 MB  

Description

A traveling salesman wants to survey N cities for business opportunities. The cities are numbered 0 through N-1, and he wishes to visit each of them at least once. He starts at city 0 and can end at any city. There are M bidirectional roads, each connecting two different cities and costing some amount of money to traverse. 
The traveling salesman also has a time machine. He can use the time machine to go back in time, without affecting which cities he is considered to have already visited. For example, suppose he has visited cities A, B, C, D, and E, in that order, and is currently in city E. He can use the time machine to go back to city A, B, C, or D. Suppose he chooses to go back to city C. At that point, he can then go back further to city A or B, but he cannot use the time machine to go forward to city D or E. Note that going back in time will not change the fact that he is considered to have already visited cities A, B, C, D, and E. 
The information of the roads will be given as (a[i], b[i], cost[i]), which means that the bidirectional road connects city a[i] and city b[i], and costs cost[i] to traverse. The cost for each road will be between 1 and 10,000,000, inclusive. For each two different cities, there will be at most one road connecting them.
He can use the time machine any number of times, and it costs nothing to use it. Find the minimum cost required to visit all the cities. Output -1 if it is impossible to visit all the cities.

Input

The first line of the input gives a number of test cases, T.
The first line of each case gives the number of cities N (1 <= N <= 1000) and the number of roads M (1 <= M <= 1000).
Next M line gives the information of each road, namely a[i], b[i] and cost[i].

Output

For each test case, output the minimum cost on each line.

Sample Input

Sample Output

3
3 3
0 1 1
0 2 1
1 2 2
6 5
0 1 2
1 4 2
4 3 3
2 4 4
0 5 3
3 1
0 2 2
2
14
-1