Minimum Cost to Connect Cities

You are given C cities and R potential roads. Each road connects two cities and has an associated cost. Your task is to compute the minimum cost required to connect all the cities such that there is a path between any two cities. This minimum cost corresponds to the cost of the Minimum Spanning Tree (MST) of the graph.

The solution can be achieved by applying Kruskal's algorithm along with a union-find (disjoint set) data structure. The MST of a connected graph with C vertices will have exactly C - 1 edges.

Note: The formula for the number of edges in a MST is given by: \(E = C - 1\).

inputFormat

The first line contains two integers C and R, where C is the number of cities and R is the number of roads. Each of the following R lines contains three integers u, v, and w, indicating there is a road between city u and city v with a cost of w.

outputFormat

Output a single integer which is the minimum cost required to connect all the cities.## sample

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

10