Minimum Spanning Tree for Trade Routes

You are given a network of outposts connected by trade routes. Each route connects two outposts and has an associated cost. Your goal is to compute the minimum total trade cost needed to connect all outposts. If it is impossible to connect all outposts, output -1.

This problem can be solved by finding the minimum spanning tree (MST) of a weighted graph using algorithms such as Kruskal's algorithm. In this problem, you are required to use techniques such as union-find with path compression and union by rank.

The MST property can be stated mathematically as follows: Find a subset of edges \(E'\) such that
\(\sum_{(u,v) \in E'} w(u,v)\) is minimized and the subgraph \((V, E')\) is connected, where V is the set of nodes and w(u,v) is the weight of the edge between nodes \(u\) and \(v\).

inputFormat

The input is given via stdin in the following format:

N P
u1 v1 w1
u2 v2 w2
... 
up vp wp

Here, the first line contains two integers, \(N\) and \(P\), where \(N\) (\(\ge 1\)) is the number of outposts and \(P\) is the number of trade routes. Each of the next \(P\) lines contains three integers \(u\), \(v\) and \(w\), representing a trade route between outposts \(u\) and \(v\) with cost \(w\). The outposts are numbered from 1 to \(N\).

outputFormat

Output the minimum total trade cost to connect all outposts via stdout. If it is impossible to connect all outposts, output -1.

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

11