Minimum Cost to Connect Cities

You are given a graph representing \( N \) cities and \( M \) flights between these cities. Each flight connects two cities with a given cost. Your task is to choose a subset of the flights such that all the cities are connected together (i.e. forming a spanning tree), and the total cost is minimized. If it is impossible to connect all the cities, output Impossible.

This problem can be solved using a minimum spanning tree algorithm, such as Kruskal's algorithm. In this approach, we first sort the flights by their cost and then iteratively add them to the spanning tree using a union-find (disjoint set union, DSU) data structure to avoid cycles.

The typical recurrence for the union-find optimization during path compression is given by:

[ \text{find}(u) = \begin{cases} u, & \text{if } parent[u] = u \ \text{find}(parent[u]), & \text{otherwise} \end{cases} ]

inputFormat

The first line of input contains two integers \( N \) and \( M \) -- the number of cities and the number of flights, respectively.

Each of the next \( M \) lines contains three integers \( u \), \( v \), and \( w \) representing a flight between city \( u \) and city \( v \) with cost \( w \). Cities are numbered from 0 to \( N-1 \).

outputFormat

Output a single line containing the minimum total cost required to connect all the cities. If it is impossible to connect all the cities, output Impossible.

## sample

4 5
0 1 10
0 2 6
0 3 5
1 3 15
2 3 4

19

</p>