A county has n towns 0 .. n-1 joined by undirected roads roads[i] = [u, v, minutes]
(parallel roads and self-loops are possible). Fire stations stand in the towns listed in
stations (all different). When the nearest station is busy, a town is covered by its
second-nearest station.
For every town, sort the driving times from that town to each station it can reach (one time per
station; a town with a station is at time 0 from it) and take the second value. Return the list
of these backup times, with -1 for a town that can reach fewer than two stations.
Examples
Input: n = 5, roads = [[0,1,2],[1,2,3],[2,3,1],[3,4,4]], stations = [0, 3]
Output: [6, 4, 5, 6, 10]
Explanation: town 2 is 5 minutes from station 0 and 1 minute from station 3,
so its backup time is 5.
Input: n = 3, roads = [[0,1,1],[1,2,1]], stations = [1]
Output: [-1, -1, -1]
Input: n = 3, roads = [[0,1,2],[1,2,2]], stations = [0, 2]
Output: [4, 2, 4]
Explanation: town 1 is 2 minutes from both stations.
Constraints
1 <= n <= 3 * 10**4,0 <= len(roads) <= 6 * 10**4,0 <= minutes <= 10**40 <= len(stations) <= n; there may be thousands of stations.
Goals
- Start one Dijkstra from many sources at once
- Let each town accept two labels that come from different stations
- Avoid running a separate search from every station