Minimum Spanning Tree

You are given N villages (numbered from 1 to N) and M bidirectional roads connecting them. Each road is described by three integers u, v, and w, indicating that there is a road between village u and village v with length w.

Your task is to determine the total length of the Minimum Spanning Tree (MST) which connects all villages. If it is impossible to connect all villages, output -1.

Recall the definition of a spanning tree: a tree that includes all vertices in a graph. The MST minimizes the sum of the weights of the edges in the spanning tree. The mathematical formulation is given by:

\(\min \sum_{e \in T} w_e\) subject to \(T\) is a spanning tree of the graph.

Note: Input is provided via stdin and output should be printed to stdout.

inputFormat

The first line contains two space-separated integers N and M, where N is the number of villages and M is the number of roads.

The following M lines each contain three space-separated integers u, v, and w representing a bidirectional road between villages u and v with length w.

outputFormat

Output a single integer, which is the total length of the Minimum Spanning Tree. If it is not possible to connect all villages, output -1.

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

7