Minimum Highway Length

You are given a network of cities and a list of possible highways connecting them. Each highway is represented as a tuple \((u, v, w)\) where \(u\) and \(v\) are cities, and \(w\) is the length of the highway connecting those cities. The goal is to determine the minimum total highway length required to connect all the cities. In other words, you should find a spanning tree for the graph with the minimum sum of weights.

If it is impossible to connect all cities, output \(-1\). If there is only one city, the required length is \(0\).

Hint: This is a classic Minimum Spanning Tree problem which can be solved efficiently using Kruskal's algorithm combined with a union-find data structure.

inputFormat

The first line contains two integers \(n\) and \(m\) where \(n\) (\(1 \leq n \leq 10^5\)) is the number of cities and \(m\) is the number of possible highways.

Each of the following \(m\) lines contains three integers \(u\), \(v\) and \(w\) representing a highway between cities \(u\) and \(v\) with length \(w\) (\(1 \leq w \leq 10^6\)).

outputFormat

Output a single integer which is the minimum total length required to connect all cities. If it is impossible to connect all the cities, output \(-1\).

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

6