Description

You are given a network of n nodes, labeled from 1 to n. You are also given an array times, where times[i] = [u, v, w] represents a directed edge from node u to node v with a travel time of w.

We will send a signal from a given node k. Return the minimum time it takes for all nodes to receive the signal. If it is impossible, return -1.

Input format:

• Line 1: JSON array times
• Line 2: Integer n
• Line 3: Integer k

Example

Input:
[[2,1,1],[2,3,1],[3,4,1]]
4
2

Output:
2

Note:

Print a single integer representing the minimum time required for all nodes to receive the signal.