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.

 

Input

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 u_i, v_i, w_i (1 ≤ u_i, v_i ≤ n,1 ≤ w_i ≤ 10⁶), which means there is an undirected edge between u_i, v_i with the weight of w_i. The graph does not contain multiple edges or self-loops.

Output

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

2
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

6
impossible

Submit

Source: 4th Kashan University's ACM Contest