Joining vertices

Time Limit: 4 Seconds    Memory Limit: 65536 KB

You are given a weighted undirected graph with n vertices and m edges. In one move you can join any two different vertices into a single vertex and the cost of this operation is the length of the shortest path between the two vertices. Please note that after joining some vertices, multiple edges or self-loops might appear in the graph. Joining vertices is continued with the induced graph until only one vertex remains.

Your task is to join all vertices into one, such that total cost of operations is minimized.



First line of input contains a single integer t (t ≤ 40), the number tests that follow. First line of each test contains integers n, m (1 ≤ n ≤ 1000,m ≤ 200000) , the number of vertices and edges in the graph, respectively. Next m lines contain three integers ui, vi, wi (1 ≤ ui, vi ≤ n,1 ≤ wi ≤ 106), which means there is an undirected edge between ui, vi with the weight of wi. The graph does not contain multiple edges or self-loops.


For each test you should output the minimum total cost of operations for contracting all vertices into one, on a single line. If it is not possible, print "impossible" instead.

Sample Input

4 5
1 2 2
3 1 1
4 3 3
2 4 3
3 2 5
4 2
1 2 10
3 4 20

Sample Output


Source: 4th Kashan University's ACM Contest