Minimum Road Length

You are given a set of N districts and M bidirectional roads connecting some pairs of these districts. Each road has an associated non-negative length. Your task is to find the minimum total length of roads required to connect all districts, so that every district is reachable from any other district. If it is impossible to connect all districts, output -1.

This problem can be solved by modeling the districts as nodes in a weighted graph and using Kruskal's algorithm to compute the Minimum Spanning Tree (MST). If the number of edges in the MST is less than N-1, then not all districts are connected.

Note: Districts are numbered from 1 to N.

inputFormat

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

N M
u1 v1 w1
u2 v2 w2
... 
vM wM

Here, the first line contains two integers N and M where N (1 ≤ N ≤ 10⁵) is the number of districts and M (0 ≤ M ≤ 10⁶) is the number of roads. Each of the next M lines contains three integers u, v (1 ≤ u, v ≤ N) and w (1 ≤ w ≤ 10⁹), representing a road connecting district u to district v with length w.

outputFormat

Print a single integer to standard output (stdout) representing the minimum total length of the roads required to connect all districts. If it is impossible to connect all districts, output -1 instead.

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

8