A network has nodes 1 .. n. Each entry (u, v, w) of times is a directed link: a signal sent from u arrives at v after w time units (w >= 0). A signal starts at node k at time 0 and travels along every link simultaneously.
Write network_delay_time(times, n, k) -> int returning the time at which the last node receives the signal, or -1 if some node never does.
network_delay_time([(2, 1, 1), (2, 3, 1), (3, 4, 1)], 4, 2) # 2
network_delay_time([(1, 2, 1)], 2, 2) # -1 (node 1 is unreachable from 2)
Links may repeat between the same pair with different weights, and a link may point from a node to itself.
Constraints: 1 <= k <= n <= 20_000, 0 <= len(times) <= 100_000, 1 <= u, v <= n, 0 <= w <= 10**4. An O(V·E) approach is too slow at this size; aim for O((V + E) log V).
Show hint
the answer is the largest of the shortest travel times from k. With non-negative weights, always settling the unsettled node with the smallest known time next (a priority queue) gives each node's shortest time exactly once.