You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges where times[i] = (ui, vi, wi). We will send a signal from a given node k. Return the minimum time it takes for all the n nodes to receive the signal. If it is impossible for all nodes to receive the signal, return -1.

Example 1:

Input:
4
3
2 1 1
2 3 1
3 4 1
k=2
Output: 2

Example 2:

Input:
2
1
1 2 1
k=2
Output: -1

Constraints:

• 1 ≤ k ≤ n ≤ 100
• 1 ≤ times.length ≤ 6000
• times[i].length == 3, 1 ≤ ui, vi ≤ n, ui ≠ vi, 1 ≤ wi ≤ 100

Input format: First line: n. Second line: number of edges. Next edges lines: u v w. Last line: k.

Output format: Minimum time or -1.