1031. Network Delay Time (Dijkstra)

A signal starts at node k in a directed weighted network with n nodes and edges [u, v, w] (travel time w). Return the time for all n nodes to receive the signal (the maximum shortest-path time from k), or -1 if some node is unreachable. The input is JSON {n, edges, k}.

Input: JSON {n, edges, k} with edges [u, v, w].

Output: Integer — the total delay time, or -1.

Examples

Input: {"n":4,"edges":[[0,1,1],[0,2,4],[1,2,1],[2,3,1]],"k":0}
Output: 3
Explanation: Farthest node is reached in 3.

Input: {"n":2,"edges":[[0,1,1]],"k":0}
Output: 1
Explanation: One hop.

Input: {"n":2,"edges":[[0,1,1]],"k":1}
Output: -1
Explanation: Node 0 unreachable from 1.

Constraints

• 1<=n<=1000
• directed
• w>=0

Asked by