Minimum Cost to Connect Cities

You are given n cities and m possible roads. Each road connects two cities and has an associated construction cost. Your task is to determine the minimum total cost to construct a network of roads that connects all the cities. If it is impossible to connect all cities, output Impossible.

This problem can be solved by finding the Minimum Spanning Tree (MST) of the graph. In an MST, the total cost is given by \(\sum_{e \in MST} w_e\), where \(w_e\) is the weight (or cost) of edge \(e\).

Note: The cities are labeled from 1 to n, and each road is bidirectional.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains two space-separated integers n and m where 1 \(\leq\) n \(\leq\) 10⁵ and 0 \(\leq\) m \(\leq\) 10⁵.
• The following m lines each contain three space-separated integers u, v, and w representing a road between cities u and v with cost w (\(1 \leq u,v \leq n\) and \(w \geq 0\)).

outputFormat

Output a single line to standard output (stdout):

• If all the cities can be connected, output the minimum total cost as an integer.
• If it is impossible to connect all cities, output Impossible.

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

9