Minimum Upgrade Cost

You are given a network of cities and roads. Each road connects two cities and has an associated upgrade cost. Your task is to determine the minimum total cost required to upgrade some roads so that every city becomes reachable from any other city. If it is impossible to connect all cities using the available roads, output -1.

This problem can be modeled as finding the Minimum Spanning Tree (MST) of a graph. Use Kruskal's algorithm (or any other MST algorithm) along with the union-find (disjoint set) data structure to efficiently compute the answer.

Note: The cities are numbered from 1 to n. Roads may connect any two distinct cities.

inputFormat

The input is given via standard input (stdin) with the following format:

n m
u1 v1 c1
u2 v2 c2
... 
um vm cm

Where:

• n is the number of cities.
• m is the number of roads.
• Each of the following m lines contains three integers: u, v, and c, indicating that there is a road connecting cities u and v with an upgrade cost c.

outputFormat

Output a single integer to standard output (stdout): the minimum cost to upgrade the roads so that every city is connected. If it is impossible to connect all the cities, output -1.

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

8