Cities are labeled 1 through n. Each entry [a, b, distance] in roads is a bidirectional road of the given distance between cities a and b.
The score of a route is the smallest road distance encountered along it. Return the minimum possible score of a route from city 1 to city n.
You may revisit any city or reuse any road, including cities 1 and n. At least one route from 1 to n exists, but other cities may be disconnected.
Example 1:
Input: n = 4
roads = [[1,2,8],[2,4,7],[2,3,2]]
Output: 2Explanation: Take the route 1 → 2 → 3 → 2 → 4. Its road distances are 8, 2, 2, and 7, so its score is 2. Reusing the road between 2 and 3 is allowed.
Example 2:
Input: n = 5
roads = [[1,5,9],[2,3,1]]
Output: 9Explanation: The only route from 1 to 5 uses their road of distance 9. The road of distance 1 is in a disconnected component and cannot be included.
Example 3:
Input: n = 3
roads = [[1,2,6],[2,3,4],[1,3,10]]
Output: 4Explanation: The route 1 → 2 → 3 has score min(6, 4) = 4. No road has a smaller distance, so 4 is the minimum possible score.
Constraints:
2 <= n <= 1000001 <= roads.length <= 100000roads[i].length == 3- Each road connects distinct city labels between
1andn. 1 <= distance <= 10000- No bidirectional road appears more than once.
- At least one route connects city
1to cityn.