The Widest Road Trip

Difficulty: 1900 4000 ms 128 MB

graphs greedy union-find

A path's width is its narrowest road. Print the maximum possible width of a path from node 1 to node N, or −1 if disconnected.

Input: the first line has N and M; each of the next M lines has u v w (road width w).

Output: the maximum bottleneck width, or −1.

Constraints:

• 2 ≤ N ≤ 10⁴
• 1 ≤ M ≤ 2×10⁴
• 1 ≤ w ≤ 10⁹

Sample Tests

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

3

3 1
1 2 9

-1

Read the Editorial