Find the minimum edge score among all roads that can lie on any path from city 1 to city n in a connected road network.
You are given an undirected road network with cities labeled from $1n$. Each road connects two cities and has a positive score.
A city path from city $1n$ may pass through any number of roads. Among all roads that belong to at least one such path, determine the smallest road score.
Return that minimum score.
Because the network is connected, at least one path from city $1n$ always exists.
Input Format
Input
- An integer , the number of cities.
- A list of roads, where each road is represented as meaning an undirected road between cities and with the given score.
Output Format
Output
- Return a single integer: the minimum score of any road that can appear on a path from city $1n$.
Constraints
Constraints
- The road network is connected.
- Roads are undirected.
- Each road score is positive.
Example 1
Input
n = 4 roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
Output
5
Explanation
City 1 and city 4 are in the same connected component. The roads that can be used on some path between them have scores 9, 6, 5, and 7, so the minimum is 5.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.