该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

现在是星际战争的最后一个年头，绝地武士想要召集他们的克隆人军队与贸易联盟决战。
但是克隆人大军分布在N个星球上，每个星球都有克隆人军队，星球从1..N编号。
经过一番深思熟虑之后，尤达大师做出了决定。
在编号为X的星球上进行决战。
星球与星球之间通过**单向通行**的传送门连接。
战舰只能通过传送门行进（不然等你到了都打完了）
但是通过传送门不能完全消除距离，所以穿过传送门i需要花费T_i的时间。
每艘战舰到达X星球后**即刻返航回到原先自己所在的星球**
（战斗太快啦根本就不耗时间而且战舰太强啦都存活了下来）
为了节约时间和燃料，所有战舰都会走耗时最短的路线。
议会想要知道，这场会战需要耗费多长的时间，所以他们请你计算战舰中最迟回到原先自己星球的时间。

Format

Input

第1行：三个整数N，M和X，(1 ≤ N ≤ 1000，1 ≤ M ≤ 100,000, 1 ≤ X ≤ N)
第2..M+1行：每行三个数字\(s_i\)，\(e_i\)和\(t_i\)表示存在一个从\(s_i\)到\(e_i\)的花费\(t_i\)时间的传送门(\(t_i\)≤100)
注意，所有的传送门都是单向的，也就是说，从A到B的耗时可能不等于B到A的耗时

Output

一行一个整数：表示战舰花费的最长时间。

Sample 1

Input

4 8 2
1 2 5
1 3 3
1 4 2
2 1 1
2 3 6
3 1 8
3 4 5
4 2 4

Output

13

Limitation

每个测试点1s,128MiB

Hint

1->2 : 5	2->1 : 1	sum = 5 + 1 = 6
3->4->2 : 9	2->1->3 : 4	sum = 9 + 4 = 13
4->2 : 4	2->1->4 : 3	sum = 4 + 3 = 7

Source

Vijos Original