A city council wants to know which roads matter for the morning commute from district s to
district t. The map has n districts 0 .. n-1 and undirected roads roads[i] = [u, v, minutes]
(minutes >= 0, parallel roads possible).
Return the sorted list of indices i such that road i lies on at least one fastest route from
s to t. If t cannot be reached, return [].
Examples
Input: n = 4, roads = [[0,1,1],[1,3,1],[0,2,1],[2,3,1],[0,3,3]], s = 0, t = 3
Output: [0, 1, 2, 3]
Explanation: two fastest routes of 2 minutes; the direct road (3 minutes) is never used.
Input: n = 3, roads = [[0,1,2],[1,2,2],[0,2,4],[0,2,5]], s = 0, t = 2
Output: [0, 1, 2]
Constraints
2 <= n <= 10**4,0 <= len(roads) <= 3 * 10**4,0 <= minutes <= 10**4,s != t- Target
O(E log V)time.
Goals
- Run Dijkstra from both ends of the trip
- Test each edge with dist_from_start + w + dist_to_end
- Check both directions of an undirected edge