A project plan has n tasks numbered 0 to n - 1, numbered so that every dependency link points from a lower-numbered task to a higher-numbered task (the plan never contains a cycle). There are m links; link i goes from task u to task v and means task v can only begin w units of time after task u finishes (this is the duration attributed to that step of the plan). Task 0 is the project's start, beginning at time 0.

The project's critical path to a given target task is the LONGEST possible total duration among all chains of dependencies from task 0 to that target (this is the earliest time by which every prerequisite chain reaching the target is guaranteed to be finished). Print the length of the critical path to the given target task. If the target task is not reachable from task 0 at all, print -1 instead.

Input format

Line 1: two integers n m. Next m lines: three integers u v w, with u < v always -- task v can begin w units after task u finishes (tasks are 0-indexed). Last line: one integer, the index of the target task.

Output format

A single integer: the length of the critical (longest) path from task 0 to the target task, or -1 if it is unreachable.

Constraints

• 1 <= n <= 1000
• 0 <= m <= 4000
• 0 <= u < v < n
• 1 <= w <= 1000
• 0 <= target task index < n

4 4
0 1 3
0 2 1
1 3 2
2 3 5
3

6

3 1
0 1 4
2

-1