Module: 动态图编程

Problem

恩去她的蘑菇森林采蘑菇。

蘑菇森林中有 m 条有向路径连接着 n 棵树。蘑菇长在每条路上。当恩走在一条路上时，他会捡起那条路上的所有蘑菇。然而，蘑菇森林拥有如此肥沃的土壤，蘑菇的生长速度非常快。恩在路上摘完蘑菇后，新的蘑菇就会长出来。也就是说，在 En 第 i 次经过该路径后，长出的蘑菇比经过之前少了 i 个。因此，如果路径最初有 x 个蘑菇，那么 En 将在第一遍中收集 x 个蘑菇，在第二个遍中收集 x - 1 个蘑菇，在第三个遍中收集 x - 1 - 2 个蘑菇，依此类推在。但是，蘑菇的数量不能小于0。
例如，让最初 9 个蘑菇生长在路径上。然后 En 将收集的蘑菇数量为 9、8、6 和 3，用于第 1 到第 4 轮。从第五关开始，恩将无法从这条路上收集任何东西（但仍然可以在上面行走）。

En决定从树s开始。仅沿着描述的路径移动，他最多可以收集多少蘑菇？

输入：
第一行包含两个整数 n 和 m (1 ≤ n ≤ 300000, 0 ≤ m ≤ 300000) —分别是蘑菇林中树木的数量和定向路径的数量。
接下来的 m 行中的每一行包含三个整数 x、y 和 w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 10⁸ ) 描述了一条从树 x 到树 y 的路径，最初有 w 个蘑菇。有从一棵树到同一棵树的路径，也有几条路径连接同一对树。
最后一行包含一个整数 s (1 ≤ s ≤ n) —恩的起始位置。

输出：
打印单个整数——恩在路上可以收集的蘑菇的最大数量。

示例：
  <正文>
说明：
在第一个例子中，En可以绕圈3圈，收集到4 + 4 + 3 + 3 + 1 + 1 = 16个蘑菇。之后，恩就没有蘑菇可以收集了。
在第二个例子中，En 可以去 3 号树，并在从 1 号树到 3 号树的路径上采摘 8 个蘑菇。

输入	输出
2 2 1 2 4 2 1 4 1	16
3 3 1 2 4 2 3 3 1 3 8 1	8