Minimum Spanning Tree

You are given an undirected weighted graph representing cities connected by roads. Your task is to compute the total weight of a Minimum Spanning Tree (MST) of the graph. A spanning tree is a subgraph that connects all vertices together without any cycles, and a minimum spanning tree is a spanning tree with the smallest possible total edge weight.

Recall that the MST of a graph \(G = (V, E)\) is such that the sum of weights of the selected edges is minimized. You may assume that the graph is connected.

This problem can be solved using Kruskal's algorithm with a union-find (disjoint-set) data structure.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of cities and the number of roads, respectively.

Each of the next \(m\) lines contains three integers \(u, v, w\) where \(u\) and \(v\) denote two cities connected by a road and \(w\) is the weight of that road.

Input is read from standard input (stdin).

outputFormat

Output a single integer representing the total weight of the Minimum Spanning Tree. The output should be written to standard output (stdout).

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

9