n cities numbered 1 to n. Roads are two-way: roads[i] = [a, b, d] is a road of length d between cities a and b. The network may be disconnected, but city n can be reached from city 1.
The **weakness** of a route is the length of its shortest road. A route may use the same road any number of times and may pass through any city, including 1 and n, more than once.
Return the smallest possible weakness of a route from city 1 to city n.n=5, roads=[[1, 2, 8], [2, 5, 6], [3, 4, 1], [1, 5, 9]] → 6
From city 1 you can only reach cities 1, 2 and 5, and the shortest road among them is 6. The road of length 1 between 3 and 4 is out of reach.
n=3, roads=[[1, 3, 10], [3, 2, 4]] → 4
The route 1 → 3 → 2 → 3 uses the road of length 4, so the answer is 4.
n is reachable from city 1n=5, roads=[[1, 2, 8], [2, 5, 6], [3, 4, 1], [1, 5, 9]]
6
Run checks the first 3 tests in your browser. Submit checks all 65 tests on the server, hidden ones included.