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