{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"题目描述","value":{"format":"MD","content":"TXT 在一个存在 $n$ 个庇护所和 $m$ 条有向路径的矿洞里采集矿物。\n\n当 TXT 经过一条路径时,他会采集路径上的矿物,但是 TXT 总是粗心大意的留下一部分矿物,所以在第二次经过同一条路径时,他还是可以采集到新的矿物。不过,随着矿物的减少,每次采集到的矿物也会减少。\n\n具体的说,当 TXT 第 $i$ 次经过一条路径后,采集到的矿物比这次经过前少 $i$ 个。\n\n也就是说,如果一条路径上最初有 $x$ 个矿物,那么 TXT 第一次会采集 $x$ 个矿物,第二次会采集 $x - 1$ 个矿物,第三次会采集 $x - 1 - 2$ 个矿物,依此类推。然而,矿物的数量永远不会少于 $0$。\n\n例如,一条路径最初有 $9$ 个矿物。当 TXT 从第一次到第四次经过时,可以从路径上采集的矿物数量分别为 $9$,$8$,$6$ 和 $3$。从第五次开始,TXT 不能从路径上采集任何矿物(但仍然可以经过它)。\n\nTXT 决定从庇护所 $s$ 开始。他只使用描述的路径,他可以采集多少矿物呢?"}},{"title":"输入格式","value":{"format":"MD","content":"第一行包含两个整数 $n$ 和 $m$ ($1 \\leq n \\leq 10^6$, $0 \\leq m \\leq 10^6$) 。\n\n接下来的 $m$ 行每行包含三个整数 $x$、$y$ 和 $w$ ($1 \\leq x, y \\leq n$,$0 \\leq w \\leq 10^8$),表示一条从庇护所 $x$ 到庇护所 $y$ 的路径,初始时有 $w$ 个矿物。\n\n最后一行包含一个整数 $s$ ($1 \\leq s \\leq n$) —— TXT 的起始位置。"}},{"title":"输出格式","value":{"format":"MD","content":"打印一个整数,表示 TXT 在他的路线上可以采集的矿物的最大数量。"}},{"title":"样例 #1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003e输入\u003c/th\u003e\n \u003cth\u003e输出\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 2\n1 2 4\n2 1 4\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e16\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"样例 #2","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003e输入\u003c/th\u003e\n \u003cth\u003e输出\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 3\n1 2 4\n2 3 3\n1 3 8\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e8\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"样例解释","value":{"format":"MD","content":"在第一个示例中,TXT 可以在圆圈上经过三次并采集 $4 + 4 + 3 + 3 + 1 + 1 \u003d 16$ 个矿物。之后,TXT 将没有矿物可以采集。\n\n在第二个示例中,TXT 可以去到庇护所 $3$ 并在从庇护所 $1$ 到庇护所 $3$ 的路径上采集 $8$ 个矿物。"}}]}