A directed graph has nodes 0 .. n-1 and edges (u, v, w) with non-negative weights. There may be self-loops and several edges between the same pair.
Write shortest_path(n, edges, src, dst) -> tuple: (distance, path) where distance is the length of a shortest path from src to dst and path is that path as a list of nodes [src, ..., dst]. If dst can't be reached, return (float("inf"), []). When src == dst the answer is (0, [src]).
If several shortest paths exist, return any one of them; the tests check that your path really uses edges of the graph and really costs distance.
edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5)]
shortest_path(5, edges, 0, 3) # (4, [0, 2, 1, 3])
shortest_path(5, edges, 0, 4) # (inf, [])
Constraints: 1 <= n <= 5 * 10^4, up to 2 * 10^5 edges, 0 <= w <= 10^4.
The large test has 50,000 nodes on a single long path, so aim for O((V + E) log V) and don't rely on deep recursion.
Show hint
while computing distances with Dijkstra, remember for every node which node its current best distance came from, and update that whenever the distance improves. Then walk those links back from dst.