Ralph and Mushrooms

题意翻译

祭此题提交12次 ------------ # 翻译 Ralph打算去蘑菇森林采蘑菇。 蘑菇森林里有n个蘑菇丛,有m条**有向的**路连接这些丛林(**可能连向自己,也可能两个丛林之间有多条路**)。经过某条路时,Ralph可以采走这条路上的全部蘑菇。然而,这是一片神奇的蘑菇森林,蘑菇被采走后会重新长出来一些。但是,第k次走过这条路后,这条路上重新长出的蘑菇会比上次少k。(举个栗子,第一次有w个蘑菇,第二次有w-1个蘑菇,第三次有w-1-2个蘑菇,以此类推……)(还有,蘑菇的数量大于0)。 那么,Ralph最多可以采到多少蘑菇呢?

题目描述

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?

输入输出格式

输入格式


The first line contains two integers $ n $ and $ m $ ( $ 1<=n<=10^{6} $ , $ 0<=m<=10^{6} $ ), 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<=10^{8} $ ), 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.

输出格式


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

输入输出样例

输入样例 #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

说明

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 $ .