A network has n nodes, labeled 1 to n. You're given times, a list of directed edges [u, v, w]: a signal takes w time to travel from u to v.
A signal is sent from node k. Return how long it takes for every node to receive it, or -1 if some node never does.
Examples
Example 1
- Input
- times = [[2, 1, 1], [2, 3, 1], [3, 4, 1]], n = 4, k = 2
- Output
- 2
Example 2
- Input
- times = [[1, 2, 1]], n = 2, k = 1
- Output
- 1
Example 3
- Input
- times = [[1, 2, 1]], n = 2, k = 2
- Output
- -1
- Why
- The only edge goes from 1 to 2, so node 1 never hears the signal.
Constraints
1 <= k <= n <= 1001 <= times.length <= 60001 <= w <= 100- There's at most one edge from any
uto anyv.