P1032金缕曲（goldknot）

【题目背景】

花庭中的道路修好以后，并肩散步渐渐成为二人每天最安静的时光。某个晚霞落满长廊的傍晚，ESC 问 Ehundategh 是否愿意陪 ESC 看看花庭之外的世界，他便在共同启程的前夜写下这阕词：

《金缕曲·对情》

千筝扶风起。稚心芳、浅驻未央，寄情留地。几番寂寂夜笙曲，泪浸枕没满衣。又复年，惊梦往醉。难触烬星万般遥，魂悠悠、愿渡银河距。九泉誓，君须记。

既忍千夫鞭辟里。再付他、点点痴妄，缄入深邸。难启陈酿对天饮，又封坛以重许。欲盼那，缘结命理。仍惧双意来晚矣，是何处、牧笛吹默语。还百年，就花取。

ESC 读完后，将一缕金线分别系在两人的行囊上。ESC 告诉 Ehundategh，这一次不必独自横渡银河，从启程到归来，他们都会走在同一段旅途中。

【题目描述】

二人的旅途从驿站 $s$ 开始。沿途共有 $n$ 处驿站，编号为 $1\sim n$，另有 $m$ 条只能沿指定方向通行的道路。第 $i$ 条道路从驿站 $u_i$ 通往驿站 $v_i$，最初散落着 $w_i$ 缕金线。道路可以连接同一座驿站，也可能有多条道路连接同一对驿站。

每当二人经过一条道路时，ESC 都会收起道路上当时所有的金线，Ehundategh 则把这段行程写进共同的纪念册。随后，这条道路会进行一次回织。若这是它第 $j$ 次被经过，那么回织出的金线比经过前少 $j$ 缕，且金线数量不会小于 $0$。

因此，一条最初有 $w$ 缕金线的道路在第一次经过时可以取得 $w$ 缕，第二次可以取得 $w-1$ 缕，第三次可以取得 $w-1-2$ 缕，依此类推。当这个数量不再为正时，之后仍可经过该道路，但无法再取得金线。

从驿站 $s$ 出发后，二人可以任意选择之后经过的道路，也可以重复经过驿站和道路。他们希望在不必分开的旅途中收集尽可能多的金线，再将这些金线一同编入纪念册。

请你求出他们最多能够取得多少缕金线。

【输入格式】

从文件 $\textbf{\textit{goldknot.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据组数。$c=0$ 表示该测试点为样例。

接下来依次输入每组测试数据。对于每组测试数据：

第一行包含两个整数 $n,m$，分别表示驿站数和道路数。

接下来 $m$ 行，每行包含三个整数 $u_i,v_i,w_i$，表示一条从驿站 $u_i$ 通往驿站 $v_i$、最初有 $w_i$ 缕金线的道路。

最后一行一个整数 $s$，表示二人出发的驿站。

【输出格式】

输出到文件 $\textbf{\textit{goldknot.out}}$ 中。

对于每组测试数据，输出一行一个整数，表示最多能够取得的金线数量。

【样例 1 输入】

10 222 231 2 442 1 45163 371 2 482 3 391 3 8101

【样例 1 输出】

11628

【说明/提示】

【样例 1 解释】

第一组测试数据中，二人可以在两个驿站之间往返，依次取得 $4,4,3,3,1,1$ 缕金线，共取得 $16$ 缕。

第二组测试数据中，直接沿道路从驿站 $1$ 前往驿站 $3$，可以取得 $8$ 缕金线。

【样例 2】

见选手目录下的 $\textbf{\textit{goldknot/goldknot2.in}}$ 和 $\textbf{\textit{goldknot/goldknot2.ans}}$。

该组样例符合测试点 $1\sim 4$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{goldknot/goldknot3.in}}$ 和 $\textbf{\textit{goldknot/goldknot3.ans}}$。

该组样例符合测试点 $5\sim 8$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{goldknot/goldknot4.in}}$ 和 $\textbf{\textit{goldknot/goldknot4.ans}}$。

该组样例符合测试点 $9\sim 12$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{goldknot/goldknot5.in}}$ 和 $\textbf{\textit{goldknot/goldknot5.ans}}$。

该组样例符合测试点 $13\sim 15$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{goldknot/goldknot6.in}}$ 和 $\textbf{\textit{goldknot/goldknot6.ans}}$。

该组样例符合测试点 $16\sim 20$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 10$，$1\leq n\leq 10^6$，$0\leq m\leq 10^6$，$1\leq u_i,v_i,s\leq n$，$0\leq w_i\leq 10^8$。单个测试点内所有测试数据的 $n$ 之和不超过 $10^6$，$m$ 之和不超过 $10^6$。

特殊性质 A：保证给出的有向道路不存在有向环。

特殊性质 B：保证任意两座驿站之间都可以沿若干条道路互相到达。

特殊性质 C：将所有能够互相到达的驿站分别合并后，设剩余 $p$ 个驿站。可以将它们依次编号为 $1\sim p$，使得对于每个 $1\leq i<p$，都至少有一条从驿站 $i$ 通往驿站 $i+1$ 的道路，且所有连接不同合并驿站的道路均为从驿站 $i$ 通往驿站 $i+1$ 的道路。