Minimal Beast Paths

Cows at John Farm want to travel freely between N grasslands numbered from 1 to N. The grasslands are separated by woods, and the cows can only use beast paths (paths discovered from wild animals) to move between grasslands. The beast paths are bidirectional and have varying lengths even if they connect the same pair of grasslands.

Each week a new beast path is discovered. The cows then have knowledge of all beast paths discovered so far, and they must choose a subset of these paths to manage. The chosen set must allow any grassland to be reached from any other, i.e. the selected paths must form a spanning tree, and the total length of the selected paths must be minimized.

If it is impossible to connect all grasslands using the available beast paths, output -1.

The edge lengths are given in \( \LaTeX \) as follows: a beast path connecting grasslands \( u \) and \( v \) has length \( w \). The goal is to find a set of beast paths such that:

[ \sum_{(u,v) \in T} w_{uv} \quad \text{is minimized}, ]

where \( T \) is the set of selected beast paths spanning all grasslands.

inputFormat

The first line contains two integers N and M where N is the number of grasslands and M is the number of beast paths discovered so far.

Each of the following M lines contains three integers u, v, and w describing a beast path connecting grasslands u and v with length w.

outputFormat

If it is possible to connect all grasslands, output the minimal total length of the selected beast paths. If it is impossible, output -1.

sample

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

4