Minimal Highway Construction Cost

You are given n stations (numbered 1 through n) and m possible highways connecting pairs of stations. Each highway has a construction cost. Your task is to choose a subset of highways to construct such that all stations become connected with the minimum total cost. If it is impossible to connect all stations with the provided highways, output -1.

This problem can be modeled using a graph where the stations are nodes and the highways are weighted edges. The goal is to find a Minimum Spanning Tree (MST) of the graph. The classical algorithm for solving this is Kruskal's algorithm (with union-find data structure) which ensures that the overall cost is minimized.

Formally, if we denote our stations set as \(V = \{1, 2, \ldots, n\}\) and the set of highways as \(E\) with each highway \((u, v, w)\) where \(w\) is the cost, then you must select a subset \(E' \subseteq E\) such that the graph \((V, E')\) is connected and

[ \text{Total Cost} = \sum_{(u,v,w) \in E'} w ]

is minimized. If no such (E') exists that spans all vertices, output -1.

inputFormat

The input is read from standard input (stdin) and consists of multiple lines:

1. The first line contains two integers n and m, where n (2 ≤ n ≤ 10^5) is the number of stations and m is the number of available highways.
2. Then, there are m lines each containing three integers u v w describing a highway connecting station u and v with cost w (1 ≤ w ≤ 10^9).

outputFormat

Output a single integer to standard output (stdout), which is the minimal total cost for constructing the highways such that all stations are connected. If it is impossible to connect all the stations, output -1.

4 5
1 2 5
1 3 3
4 1 6
2 4 7
3 4 4

12