Minimum Spanning Tree

You are given an undirected weighted graph with \(N\) nodes and \(M\) edges. Your task is to compute the minimum total weight that connects all nodes, i.e. the weight of the Minimum Spanning Tree (MST). Use Kruskal's algorithm with a Union-Find data structure to achieve an optimal solution.

Note: The MST is defined as a subset of the edges that connects all nodes together without any cycles and with the minimum possible total edge weight. Formally, if \(T\) is the MST then:

[ \min \sum_{e \in T} w_e ]

where \(w_e\) is the weight of edge \(e\).

inputFormat

The first line of input contains two integers \(N\) and \(M\) denoting the number of nodes and the number of edges respectively.

The next \(M\) lines each contain three integers \(u\), \(v\), and \(w\) representing an undirected edge between nodes \(u\) and \(v\) with weight \(w\).

\(1 \leq u,v \leq N\)

outputFormat

Output a single integer which is the total weight of the Minimum Spanning Tree.

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

9