Minimum Travel Cost

You are given a set of cities and bidirectional roads connecting them. Each road has an associated travel cost. Your task is to determine the minimum total cost required to travel such that every city is visited at least once. In other words, you must determine the cost of the Minimum Spanning Tree (MST) for the graph. If it is impossible to visit all cities (i.e. the graph is disconnected), you should output impossible. Note that when there is only one city and no roads, the cost is defined as 0.

Input Format:

• The first line contains an integer T, representing the number of test cases.
• For each test case, the first line contains two integers N and M, denoting the number of cities and the number of roads respectively.
• The following M lines each contain three integers u, v, and w where u and v are the cities connected by a road and w is its cost.

Output Format:

• For each test case, output a single line. If it is possible to visit all cities, print the minimum travel cost, otherwise print impossible.

The underlying algorithm typically involves constructing an MST using Kruskal's algorithm. The connection between cities can be formulated using the Union-Find (Disjoint Set Union) data structure.

inputFormat

The input is provided via stdin in the following format:

T
N1 M1
u1 v1 w1
u2 v2 w2
... (M1 lines for test case 1)
N2 M2
... (M2 lines for test case 2)
...

Where T is the number of test cases. For each test case, the first line contains two integers: N (number of cities) and M (number of roads). The following M lines describe the roads.

outputFormat

The output is printed to stdout. For each test case, print a single line with the total minimum cost required to connect all the cities. If the cities cannot all be connected, print impossible.

## sample

2
4 4
1 2 4
2 3 2
3 4 1
4 1 5
3 3
1 2 6
2 3 8
3 1 5

7
11

</p>