Slowest Signal Arrival

A network has `n` nodes labeled 0..n-1 and directed edges given as [u, v, w] meaning a signal travels from u to v in w time. A signal starts at node `s`. Return the time for the signal to reach every node (the maximum shortest-path time from s), or -1 if some node is unreachable.

Examples

in: n = 4, edges = [[0,1,1],[0,2,4],[1,2,1],[2,3,1]], s = 0

out: 3

node 3 is reached at time 3

in: n = 2, edges = [[0,1,5]], s = 0

out: 5

one hop

Constraints

1 <= n <= 1000
0 <= u, v < n
1 <= w <= 10^6

Hints

target: O(E log V) time⌘↩ run · ⇧⌘↩ submit