Short roads X50299

Consider the map of a country, with n cities (numbered between 0 and n−1) and m unidirectional roads that connect them. Each road has a certain length. We want to go from city 0 to city 1. As we travel with people prone to get carsick, and we do not want to stop halfway to stretch our legs, we want to follow the route such that the longest road we take is as short as possible. That is, if the route uses k roads, with lengths ℓ₁, ⋯, ℓ_k, and ℓ = max(ℓ₁, ⋯, ℓ_k), we want ℓ to be as small as possible.

Input

The input consists in several cases. Each case begins with n and m, followed by m triplets x y ℓ, with x ≠ y, indicating a road that goes from x to y of length ℓ. Assume 2 ≤ n ≤ 10⁴, 1 ≤ m ≤ 10n, that there is at most one road from x to y in this order, that the lengths are between 1 and 10⁵, and that there is always a route between 0 and 1.

Output

For each case, write the maximum length of the roads of the best possible route.

The second line of the example of output corresponds to the route 0 → 4 → 2 → 1, which has a road (the 0 → 4) of maximum length 80.

Hint

Consider a variant of Dijkstra’s algorithm.