Problem J: 动物王国的聚会

Problem J: 动物王国的聚会

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 149  Solved: 37
[Submit] [Status] [Web Board] [Creator:]

Description

狮子王想开宴会。所有动物都会去,而且都想快点去(你们懂得),所以他们都会走最快的路经。聚会完了!他们有都想快点回家(你们懂得)。在路上所花的最长时间

       

 

Input

第一行输入三个整数NMX1N1000)(0M100000)—表示一共有N个动物,M条路,狮子王的编号X

接下来M行每行三个整数a,b,cab的时间为cb不一定到a)。

数据保证为int范围



Output

对于每一个样例输出在路上所花的最长时间。

Sample Input Copy

4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3

Sample Output Copy

10