Minimum Road Length

You are given an undirected weighted graph representing provinces connected by roads. Each road connects two provinces and has a length. Your task is to determine the minimum total length of roads needed to connect all provinces. If it is impossible to connect all provinces, output -1.

Formally, you are given two integers N and M, representing the number of provinces and the number of roads respectively. Following this, there are M lines, each containing three integers u, v, and w that denote a bidirectional road between provinces u and v with length w. The objective is to choose a subset of these roads such that all provinces are connected and the sum of the road lengths is minimized. This is equivalent to finding a Minimum Spanning Tree (MST) of the graph.

The problem can be represented mathematically as: \[ \min\sum_{e \in T} w(e) \] where \(T\) is the set of edges in the spanning tree.

inputFormat

The input is read from stdin. The first line contains two space-separated integers N and M, where N is the number of provinces and M is the number of roads available. Each of the next M lines contains three space-separated integers u, v, and w describing a road that connects province u and province v with length w.

outputFormat

Output a single integer to stdout: the minimum total road length required to connect all provinces. If it is impossible to connect all provinces, output -1.

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

6