← 返回题目列表

Codeforces · 894/E

E. 拉尔夫和蘑菇

中文机器翻译题面 查看原题

拉尔夫要去蘑菇森林里采集蘑菇。

蘑菇森林中有 m 条有向路径连接 n 棵树。每条道路上都长有一些蘑菇。当拉尔夫经过一条小路时,他会收集路上所有的蘑菇。蘑菇森林拥有一片神奇的沃土,蘑菇以惊人的速度生长。拉尔夫完成路上的蘑菇收集后,新的蘑菇就会重新生长。更具体地说,拉尔夫第 i 次经过一条路径后,重新长出的蘑菇数量比这次经过之前要少。也就是说,如果一条路径上最初有 x 个蘑菇,那么拉尔夫将第一次收集 x 个蘑菇,第二次收集 x - 1 个蘑菇,第三次收集 x - 1 - 2 个蘑菇,依此类推。但是,蘑菇的数量永远不能少于0。

例如,假设路径上最初有 9 个蘑菇。当拉尔夫第一次到第四次经过该路径时,可以收集的蘑菇数量为 9、8、6 和 3 个。从第五次开始,拉尔夫就无法从这条路上收集任何蘑菇了(但仍然可以通过它)。

拉尔夫决定从树s开始。仅使用描述的路径他可以收集多少蘑菇?

输入

第一行包含两个整数n和m(1≤n≤106,0≤m≤106),分别表示蘑菇森林中树的数量和有向路径的数量。

以下 m 行中的每一行都包含三个整数 x、y 和 w (1 ≤ x, y ≤ n, 0 ≤ w ≤ 108),表示从 x 树到 y 树的路径,最初有 w 个蘑菇。可以存在从树到其自身的路径,以及同一对树之间的多条路径。

最后一行包含一个整数 s (1 ≤ s ≤ n) — Ralph 的起始位置。

输出

打印一个整数,表示拉尔夫在他的路线上可以收集的蘑菇的最大数量。

示例

输入 #1

2 2
1 2 4
2 1 4
1

输出 #1

16

输入 #2

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

输出 #2

8

注意

在第一个样本中,拉尔夫可以在圆圈上经过 3 次,并收集 4 + 4 + 3 + 3 + 1 + 1 = 16 个蘑菇。之后拉尔夫就不会再收集蘑菇了。

在第二个示例中,Ralph 可以前往 3 号树并在从 1 号树到 3 号树的路径上收集 8 个蘑菇。