Cheapest Power Grid
Connect villages to one power grid. Building line u v costs . Choose lines so every village is connected at minimum total cost (a minimum spanning tree — try Kruskal's algorithm). Print IMPOSSIBLE if they can't all be connected.
Input
and , then lines u v w.
Output
The minimum total cost or IMPOSSIBLE.
Constraints
,
Sample 1
Input
4 5 1 2 1 2 3 4 1 3 3 3 4 2 2 4 5
Output
6
Sample 2
Input
3 1 1 2 5
Output
IMPOSSIBLE