题目描述

据说，在那遥远的一个山上有n个村民，每个村民都有自己的一个房子，因为这些村民每天白天都要干农活， 所以晚上就成他们的娱乐时间，每天晚上这些村民从自己家出发，会聚集到村民x家唠嗑儿（村民x晚上就不会出门）， 唠完嗑儿后就各回各家。因为这些村民白天干活，到晚上就会很疲惫，所以他们去村民x家和从村民x到自己家都走最短路。 从这些最短路(去村民x家+从村民x到自己家)里找出最大值输出。

输入描述

第一行给出3个整数n，m，x ：n代表n个村民，m代表有m条有向边，x代表会在编号为x的村民家唠嗑儿。 接着给出m行，每行3个整数 a , b, c : 表示村民a到村民b 的路径为c。

输出描述

输出所有村民中最短路里的最大值。

样例输入

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

样例输出

5

数据范围

1<=n<=1000, 1<=m<=100000, 1<=c<=100