Minimum Cost to Connect Cities

You are given a set of cities numbered from 1 to n and a list of bidirectional roads. Each road is represented by three integers u, v and w where there is a road between city u and city v with cost w. Your task is to determine the minimum cost required to connect all the cities such that any city can reach any other city. If it is impossible to connect all cities, output -1.

This problem is equivalent to finding the Minimum Spanning Tree (MST) of a weighted undirected graph. Recall that if the graph has n nodes, a spanning tree will have exactly $n-1$ edges. Use union-find or Kruskal's algorithm to implement an efficient solution.

Note: If there is only one city, the cost is 0. If there are no roads and more than one city, then it is impossible to connect all cities, and the answer is -1.

inputFormat

The first line contains two integers n and m — the number of cities and the number of roads.

Each of the next m lines contains three integers u, v and w describing a road between cities u and v with cost w.

Constraints:

• $1 \leq n \leq 10^5$
• $0 \leq m \leq 10^5$
• $1 \leq u, v \leq n$
• $1 \leq w \leq 10^9$

outputFormat

Output a single integer: the minimum cost to connect all cities, or -1 if it is impossible.

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

6