Maximum Edge Weight in Minimum Spanning Tree

Given a connected, undirected graph with N nodes and M edges, where each edge has an associated weight, your task is to compute the maximum edge weight in the graph's Minimum Spanning Tree (MST). You are required to use Kruskal's algorithm along with a Union-Find data structure to solve the problem.

The MST of a graph is defined as a spanning tree that minimizes the total edge weight. In this problem, instead of computing the sum, you need to determine the weight of the heaviest edge included in the MST. Formally, if the MST contains edges with weights \(w_1, w_2, \ldots, w_{N-1}\), you are to compute \(\max\{w_1, w_2, \ldots, w_{N-1}\}\).

Note: It is guaranteed that the graph is connected, hence an MST always exists.

inputFormat

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

Each of the next \(M\) lines contains three integers \(u\), \(v\), and \(w\) indicating that there is an edge between node \(u\) and node \(v\) with weight \(w\).

Nodes are numbered from 1 to \(N\).

outputFormat

Output a single integer, the maximum weight of an edge in the Minimum Spanning Tree of the graph.

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

3