Minimum Cost to Build the Rail Network

You are given a set of cities and potential rail connections between them. Each connection has an associated cost, and the goal is to determine the minimum total cost to connect all cities using these connections.

This problem is equivalent to finding the Minimum Spanning Tree (MST) of a graph. If it is impossible to connect all cities, output IMPOSSIBLE.

Note: Use \(N-1\) edges to connect \(N\) cities in the MST. The formula for the number of required edges is \(N - 1\).

inputFormat

The first line of input contains two integers \(N\) and \(M\), where \(N\) is the number of cities and \(M\) is the number of potential rail connections. Each of the following \(M\) lines contains three integers \(u\), \(v\), and \(w\), indicating that there is a possible connection between city \(u\) and city \(v\) with cost \(w\>.

outputFormat

If all cities can be connected, output the minimum total cost required to build the rail network. Otherwise, output IMPOSSIBLE. The output should be printed to stdout.

4 5
1 2 5
1 3 10
2 3 4
2 4 3
3 4 8

12