CF894E.Ralph and Mushrooms

Ralph is going to collect mushrooms in the Mushroom Forest.

There are m directed paths connecting n trees in the Mushroom Forest. On each path grow some mushrooms. When Ralph passes a path, he collects all the mushrooms on the path. The Mushroom Forest has a magical fertile ground where mushrooms grow at a fantastic speed. New mushrooms regrow as soon as Ralph finishes mushroom collection on a path. More specifically, after Ralph passes a path the i-th time, there regrow i mushrooms less than there was before this pass. That is, if there is initially x mushrooms on a path, then Ralph will collect x mushrooms for the first time, x - 1 mushrooms the second time, x - 1 - 2 mushrooms the third time, and so on. However, the number of mushrooms can never be less than 0.

For example, let there be 9 mushrooms on a path initially. The number of mushrooms that can be collected from the path is 9, 8, 6 and 3 when Ralph passes by from first to fourth time. From the fifth time and later Ralph can't collect any mushrooms from the path (but still can pass it).

Ralph decided to start from the tree s. How many mushrooms can he collect using only described paths?

拉尔夫将前往蘑菇森林采集蘑菇。

蘑菇森林中有 $m$ 条有向路径，连接着 $n$ 棵树。每条路径上生长着若干蘑菇。当拉尔夫经过一条路径时，他会采集该路径上的全部蘑菇。蘑菇森林拥有一片神奇的肥沃土地，蘑菇以惊人的速度再生。每当拉尔夫完成一次路径上的蘑菇采集后，该路径上的蘑菇会立即重新生长。具体而言：拉尔夫第 $i$ 次经过某条路径后，新长出的蘑菇数量比本次采集前少 $i$ 个。也就是说，若某条路径初始有 $x$ 个蘑菇，则拉尔夫第一次经过时可采集 $x$ 个蘑菇，第二次经过时可采集 $x - 1$ 个蘑菇，第三次经过时可采集 $x - 1 - 2 = x - 3$ 个蘑菇，依此类推。但蘑菇数量永远不会低于 $0$。

例如，假设某条路径初始有 $9$ 个蘑菇，则拉尔夫从第一次到第四次经过该路径时，分别可采集 $9$、$8$、$6$ 和 $3$ 个蘑菇；从第五次及之后经过该路径时，拉尔夫无法再采集到任何蘑菇（但仍可通行）。

拉尔夫决定从树 $s$ 出发。他仅能使用上述描述的路径，最多能采集多少蘑菇？

The first line contains two integers n and m (1 ≤ n ≤ 106, 0 ≤ m ≤ 106), representing the number of trees and the number of directed paths in the Mushroom Forest, respectively.

Each of the following m lines contains three integers x, y and w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 108), denoting a path that leads from tree x to tree y with w mushrooms initially. There can be paths that lead from a tree to itself, and multiple paths between the same pair of trees.

The last line contains a single integer s (1 ≤ s ≤ n) — the starting position of Ralph.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 10^6$，$0 \leq m \leq 10^6$），分别表示蘑菇森林中树的数量和有向路径的数量。

接下来的 $m$ 行每行包含三个整数 $x$、$y$ 和 $w$（$1 \leq x, y \leq n$，$0 \leq w \leq 10^8$），表示一条从树 $x$ 指向树 $y$ 的路径，其上初始有 $w$ 个蘑菇。可能存在从一棵树指向其自身的路径，以及同一对树之间存在多条路径。

最后一行包含一个整数 $s$（$1 \leq s \leq n$）—— Ralph 的起始位置。

Print an integer denoting the maximum number of the mushrooms Ralph can collect during his route.

输出一个整数，表示拉尔夫在路线中最多能采集的蘑菇数量。

In the first sample Ralph can pass three times on the circle and collect 4 + 4 + 3 + 3 + 1 + 1 = 16 mushrooms. After that there will be no mushrooms for Ralph to collect.

In the second sample, Ralph can go to tree 3 and collect 8 mushrooms on the path from tree 1 to tree 3.

在第一个样例中，拉尔夫可以在环上经过三次，收集到 $4 + 4 + 3 + 3 + 1 + 1 = 16$ 个蘑菇。此后将不再有蘑菇可供拉尔夫收集。

在第二个样例中，拉尔夫可以前往第 3 棵树，并在从第 1 棵树到第 3 棵树的路径上收集到 8 个蘑菇。