测试数据来自 system/2199

作业已超过截止时间，您无法递交本题目。

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小H所在的城市有 \(n\) 个居民点，每个居民点都有一个朋友要参加在小H的生日派对，小H住在 \(s\) 号居民点。共有 \(m\) 条单向路连接着居民点，第 \(i\) 条路需要 \(t_i\) 的时间来通过。

　　朋友们都很懒，所以不管是前去 \(s\) 居民点参加派对还是返回住所，她们都采用了用时最少的路线。那么，用时最多的朋友需要多少时间来回呢？

【输入格式】

　　第一行是三个用空格隔开的整数：\(n,m,s\)。
　　第二行到第 \(m+1\) 行,每行三个用空格隔开的整数: \(a_i,b_i\) 以及 \(t_i（1≤a_i,b_i≤n，1≤t_i≤100）\)。表示一条道路的起点，终点和需要花费的时间。

【输出格式】

　　一个整数，表示所有参加聚会的朋友中，用时最多的朋友需要的时间。

【输入输出样例】

　Input

4 7 1
1 2 1
2 1 4
2 3 2
3 1 1
3 4 1
4 3 2
4 1 4

　Output

7

【数据限制】

　　100%的数据满足：\(1≤x≤n≤1000\)，\(1≤m≤100000\)，保证从任何一个居民点出发都能到达s，且从s出发可以到达其他所有居民点。

【来源】

　　Mr.he