Galaxy Connection

You are given a galaxy with n planets and m bidirectional routes. Each route connects two different planets with a certain cost.

Your task is to determine the minimum cost required to connect all planets such that every planet is reachable from any other planet. If it is not possible to connect all the planets, output IMPOSSIBLE.

This problem can be modeled as finding the Minimum Spanning Tree (MST) in a weighted graph. One popular algorithm for solving this problem is Kruskal's algorithm, which uses a Union-Find data structure with path compression and union by rank to efficiently merge sets.

The cost of the MST can be computed as the sum of weights of the edges included in the tree. Mathematically, if we let \(E'\) be the set of edges in the MST, the answer is \(\sum_{e \in E'} w_e\) provided the MST spans all \(n\) vertices. Otherwise, if a spanning tree does not exist, output IMPOSSIBLE.

inputFormat

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

• The first line contains two integers n and m where n is the number of planets and m is the number of routes.
• The next m lines each contain three integers u, v, and w, indicating that there is a route between planet u and planet v with a cost of w.

Note: Planets are numbered from 1 to n.

outputFormat

Print a single line to standard output (stdout) containing the minimum cost required to connect all planets. If it is impossible to connect all planets, print IMPOSSIBLE.

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

6