Minimum Total Road Length

You are given n buildings numbered from 1 to n and m roads connecting them. Each road is represented by three integers u, v, and w, describing a road between building u and building v with length w.

Your task is to determine if it is possible to connect all the buildings by selecting a subset of the roads. If it is possible, you must compute the minimum total road length required to connect all buildings. Otherwise, output -1.

This problem is equivalent to finding a Minimum Spanning Tree (MST) in a graph. Formally, you are looking for a set of roads such that all buildings are connected and the total weight w is minimized, i.e., $$\min \sum_{i \in MST} w_i.$$

If the graph is not connected, the answer should be -1.

inputFormat

The input is given via stdin in the following format:

N M
u1 v1 w1
u2 v2 w2
... 
um vm wm

where:

• N is the number of buildings.
• M is the number of roads.
• Each of the next M lines contains three integers describing a road between two buildings u and v with length w.

outputFormat

Output a single integer via stdout: the minimum total road length required to connect all buildings, or -1 if it is impossible.

## sample

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

11