Minimum Cost to Connect Cities

You are given a network of n cities and m roads. Each road connects two cities and has a cost associated with its construction. Your task is to determine the minimum total cost required to connect all the cities directly by constructing additional roads where necessary. If it is impossible to connect all the cities, output -1.

This problem can be modeled as finding the Minimum Spanning Tree (MST) of a weighted graph. The MST cost is given by:

where \(T\) is the set of edges selected in the MST and \(w(e)\) is the cost (weight) of edge \(e\). Use an efficient algorithm, for example Kruskal's algorithm with union-find, to solve the problem.

inputFormat

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

• The first line contains two integers n and m separated by a space, where n is the number of cities and m is the number of roads.
• The next m lines each contain three space-separated integers: u, v, and w, representing a road between city u and city v with construction cost w.

outputFormat

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

4 3
1 2 1
2 3 4
3 4 5

10