拉尔夫要去蘑菇森林里采集蘑菇。
蘑菇森林中有 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 个蘑菇。