A network has n nodes labelled 1..n connected by m one-way links. A link u v w means a signal takes w time units to travel from u to v. A signal is emitted from a source node s and travels along links, always by the fastest route.

Report the time at which the last node receives the signal, i.e. the maximum over all nodes of the shortest travel time from s. If any node can never receive the signal, report -1.

Input format

Line 1: two integers n and m. The next m lines each contain three integers u v w, a directed link from u to v with travel time w. The final line contains one integer s, the source node.

Output format

A single integer: the time for the signal to reach every node, or -1 if some node is unreachable.

Constraints

• 1 <= n <= 2000
• 0 <= m <= 20000
• 1 <= u, v, s <= n
• 1 <= w <= 1000
• There may be several links between the same ordered pair; the faster one applies.

4 4
1 2 1
1 3 4
2 3 1
3 4 1
1

3

3 1
1 2 5
1

-1