Minimizing the Longest Road in an Optimal Network

You are given n cities and m roads connecting these cities. Each road has an associated travel time. Your task is to build a network that connects all the cities such that the longest road used in the network is as short as possible.

Formally, consider an undirected weighted graph \(G=(V,E)\) where each edge \(e\in E\) has a weight \(w(e)\). Find a spanning tree \(T\subseteq G\) which minimizes the quantity \(\max_{e\in T} w(e)\). If the cities cannot be fully connected, output 0.

inputFormat

The first line contains two integers n and m representing the number of cities and the number of available roads respectively.

Each of the following m lines contains three integers u, v, and w, where there is a road between city u and city v with a travel time of w.

outputFormat

Output a single integer: the minimum possible value of the longest road in a spanning tree that connects all cities. If it is not possible to connect all cities, print 0.

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

5