Taco Danger Path

You are given an undirected, connected graph with n cities (nodes) and m bidirectional roads (edges). City 1 is the capital. Each road has an associated danger level.

For each city, define its danger level as the minimum possible maximum road danger encountered on any path from the capital to that city. Your task is to compute the worst-case scenario, i.e. the maximum value among these minimum danger levels for all cities (from city 2 to city n).

The problem can be formulated as follows: Find \( d = \max_{i=2}^n \min_{\text{paths from 1 to } i} \max_{\text{edge } e \in path} w_e \), where \(w_e\) is the danger level of edge \(e\).

The input is guaranteed to describe a connected graph.

inputFormat

The input is read from standard input (stdin). The first line contains two integers n and m, representing the number of cities and roads respectively. Each of the following m lines contains three integers u v w, indicating a bidirectional road between cities u and v with danger level w.

outputFormat

The output is written to standard output (stdout) and should be a single integer: the worst-case (maximum) minimum danger level among all paths from the capital (node 1) to every other city.

3 3
1 2 10
1 3 20
2 3 30

20