Second shortest path

Write codeHard40 min

Your task

A directed graph on n nodes (0..n-1) has edges [u, v, w] with positive weights. Return the length of the SECOND shortest path from s to t, where 'second shortest' is the smallest path length strictly greater than the shortest path length. Paths may revisit nodes (they are walks), so a second-shortest can reuse vertices. Return -1 if no such second distinct length exists (or t is unreachable). Constraints: 1 <= n <= 2000; 1 <= w <= 10^6.

Examples

second_shortest(n: int, edges: list[list[int]], s: int, t: int) -> int

Example 1

Inputsecond_shortest(4, [[0, 1, 1], [1, 3, 2], [0, 2, 1], [2, 3, 3], [0, 3, 5]], 0, 3)

Output4