Minimum Road Length

You are given a set of n locations (numbered from 1 to n) and m potential roads connecting these locations. Each potential road connects two locations, u and v, with a given length w. Your task is to compute the minimum total length of roads required to connect all the locations. If it is not possible to connect all the locations, output -1.

This problem can be modeled as finding the Minimum Spanning Tree (MST) of a weighted undirected graph. By using algorithms such as Kruskal's or Prim's, you can determine the minimum length required. In this problem, we use the union-find data structure to implement Kruskal's algorithm.

Note: If there is only one location, the answer is 0, because no road is needed.

The mathematical formulation for the MST is given by:

$$\min \sum_{(u,v) \in T} w(u,v)$$

subject to \(T\) being a spanning tree of the graph.

inputFormat

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

n m
u1 v1 w1
u2 v2 w2
... 
um vm wm

Here:

• n is the number of locations (1 ≤ n ≤ 10^5).
• m is the number of potential roads.
• Each of the next m lines contains three integers u, v (the endpoints of the road), and w (the length of the road), separated by spaces.

outputFormat

Output a single integer to stdout: the minimum total length of roads required to connect all locations, or -1 if it is not possible.

## sample

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

6