Each edge in times is [source, target, weight], meaning a signal can travel from source to target in weight time. The graph is directed, so an edge from a to b does not imply an edge from b to a.
Nodes are labeled from 1 through n, and the signal starts at node k at time 0. Once a node receives the signal, it can immediately forward it along its outgoing edges.
Return the time when the last reachable node receives the signal. This is the largest shortest-path distance from k; if any node cannot be reached, return -1.
Examples
Input: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2 Output: 2
Input: times = [[1,2,1]], n = 2, k = 2 Output: -1
Constraints
- 1 <= k <= n <= 100
- 1 <= times.length <= 6000
- 0 <= wi <= 100