Minimum Cost to Connect All Cities

You are given a network of N cities and M bidirectional roads connecting them. Each road is defined by a triplet (u, v, w) where u and v are the cities connected by the road, and w is the cost to build that road. Your task is to determine the minimum total cost required to connect all the cities. If it is impossible to connect all cities, output -1.

This problem can be modeled as finding the Minimum Spanning Tree (MST) of a graph. Recall that for a connected graph with N nodes, a spanning tree has exactly N-1 edges. The MST is the spanning tree with the minimum possible sum of edge weights.

Constraints:

• The cities are numbered from 1 to N.
• If the number of roads provided is less than N-1, it is impossible to connect all the cities.

In mathematical terms, given that the cities and roads can be represented as a graph \(G = (V, E)\) where \(|V|=N\) and \(|E|=M\), you need to determine the minimum cost \(C\) such that:

\[ C = \sum_{e \in T} w_e\, , \quad \text{with } |T| = N-1 \]

or output -1 if no such spanning tree exists.

inputFormat

The input is read from standard input (stdin) and has the following format:

N M
u1 v1 w1
u2 v2 w2
... 
uM vM wM

where:

• N is the number of cities.
• M is the number of roads.
• Each of the next M lines contains three integers u, v, and w representing a road between city u and city v with cost w.

outputFormat

Output a single integer to standard output (stdout) which is the minimum total cost to connect all the cities. If it is impossible to connect all cities, output -1.

## sample

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

9