A project has n tasks numbered 0 to n - 1, numbered in an order consistent with their dependencies: every prerequisite link only ever points from a lower-numbered task to a higher-numbered task, so the task graph never contains a cycle. There are m such links; a link from task u to task v with weight w means that once task u is finished, task v can be finished w minutes later (assuming v's other prerequisites, if any, are also satisfied at least that early). Task 0 is always the project's starting task and is finished at time 0.

Print the earliest possible time a given target task can be finished, taking the fastest chain of dependencies into account. If the target task can never be finished (it is not reachable from task 0), 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 finish w minutes after task u finishes (tasks are 0-indexed). Last line: one integer, the index of the target task.

Output format

A single integer: the earliest completion time of 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 2
0 2 5
1 2 1
2 3 2
3

5

3 1
0 1 4
2

-1