Heaviest Road in Optimal Network

An optimal communication network is required to minimize the longest travel time between any two cities. Given n cities and m roads, you need to select a subset of roads that connects all cities with the minimum possible maximum road weight.

This problem is equivalent to finding a Minimum Spanning Tree (MST) of a connected graph. The answer is the weight of the heaviest road (edge) in the MST. Formally, if the selected edges of the MST are \(e_1, e_2, \dots, e_{n-1}\) with weights \(w_1, w_2, \dots, w_{n-1}\), the output should be \(\max(w_1, w_2, \dots, w_{n-1})\).

inputFormat

The first line of the input contains two integers \(n\) (the number of cities) and \(m\) (the number of roads), separated by a space.

Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(w\), indicating a road connecting city \(u\) with city \(v\) that has a weight of \(w\).

outputFormat

Output a single integer representing the weight of the heaviest road in the optimal communication network.

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

4