Problem
En goes to her Mushroom Forest to gather mushrooms.
There are m oriented paths in the Mushroom Forest connecting n trees. Mushrooms grow on every path. When En walks along a path, he picks up all the mushrooms on that path. However, the Mushroom Forest has such fertile soil that mushrooms grow at a fantastic rate. New mushrooms grow as soon as En finishes picking mushrooms on the path. Namely, after En passes along the path for the i-th time, grows i fewer mushrooms than it was before this passage. Thus, if the path initially had x mushrooms, then En will collect x mushrooms in the first pass, x - 1 mushroom in the second, x - 1 - 2 mushrooms in the third, and so on. However, the number of mushrooms cannot become less than 0.
For example, let initially 9 mushrooms grow on the path. Then the number of mushrooms that En will collect is 9, 8, 6, and 3 for passes one through four. From the fifth pass onwards, En won't be able to collect anything from this path (but can still walk on it).
En decided to start from tree s. What is the maximum number of mushrooms he can collect by moving only along the described paths?
Input:
The first line contains two integers n and m (1 ≤ n ≤ 300000, 0 ≤ m ≤ 300000) — the number of trees and the number of oriented paths in the Mushroom Forest, respectively.
Each of the next m lines contains three integers x, y and w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 10
8 ) describing a path that leads from tree x to tree y with w mushrooms initially. There are paths that lead from a tree to the same tree, as well as several paths connecting the same pair of trees.
The last line contains a single integer s (1 ≤ s ≤ n) — En's starting position.
Output:
Print a single integer — The maximum number of mushrooms that En can collect on her way.
Examples:
| Input |
Output |
2 2
1 2 4
2 1 4
1 |
16 |
3 3
1 2 4
2 3 3
1 3 8
1 |
8 |
Explanations:
In the first example, En can go around the circle three times and collect 4 + 4 + 3 + 3 + 1 + 1 = 16 mushrooms. After that, there will be no mushrooms for En to collect.
In the second example En can go to tree 3 and pick 8 mushrooms on the path from tree 1 to tree 3.