Last Edge Weight Before Disconnection

Given a connected undirected graph \( G \) with \( n \) nodes and \( m \) edges, two players play a game by picking edges optimally to maintain the connectivity of the graph. The game stops when adding any remaining edge would disconnect the graph. Your task is to determine the maximum weight of an edge that could be the last edge added before the graph becomes disconnected.

In other words, if we build the Minimum Spanning Tree (MST) of the graph using Kruskal's algorithm, the answer is the weight of the last edge added to the MST. This is equivalent to the heaviest edge in the MST.

Input Format Explanation: The first line of input contains two integers \( n \) and \( m \). The next \( m \) lines each contain three integers \( u \), \( v \), and \( w \) representing an edge between nodes \( u \) and \( v \) with weight \( w \). All node indices are 1-indexed.

Note: It is guaranteed that the input graph is connected.

inputFormat

The input is given via standard input (stdin). The format is as follows:

n m
u1 v1 w1
u2 v2 w2
... 
um vm wm

where \( n \) is the number of nodes, \( m \) is the number of edges, and each subsequent line represents an edge of the graph.

outputFormat

Output a single integer to standard output (stdout), which is the weight of the last edge added to the minimum spanning tree (i.e., the heaviest edge in the MST).

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

4