A commuter wants a backup route. The town has n stops 0 .. n-1 and undirected roads
roads[i] = [u, v, t] taking t minutes (t >= 1). A walk from stop 0 to stop n-1 may revisit
stops and reuse roads. Return the duration of the second-shortest walk, i.e. the smallest walk
duration that is strictly greater than the shortest one. Return -1 if no such walk exists.
Examples
Input: n = 3, roads = [[0,1,1],[1,2,1],[0,2,3]]
Output: 3
Explanation: the shortest walk 0-1-2 takes 2; the direct road takes 3.
Input: n = 2, roads = [[0,1,5]]
Output: 15
Explanation: after 0-1 (5), the next option is 0-1-0-1 (15).
Input: n = 3, roads = [[0,1,2],[1,2,2],[0,2,4]]
Output: 8
Explanation: 0-1-2 and 0-2 both take 4; the next distinct duration is 8.
Constraints
1 <= n <= 5000,0 <= len(roads) <= 10**4,1 <= t <= 10**6- Target
O(E log V)time.
Goals
- Track two distance values per node instead of one
- Relax a candidate into the correct slot
- Allow walks that revisit nodes