说明

在广袤的卡拉迪亚大陆上，战争连年不断，而爱情是永恒的主题。

现在你的大人----斯瓦迪亚的一国之君哈劳斯决定对罗多克王国的光头发动最后的攻击。

哈劳斯决定采取骚扰循环攻击战术进行攻击。

也就是，帝国的每座城都派出一支军队，前往杰尔喀拉进行骚扰攻击，骚扰结束后，这支军队会回到他出发的城镇进行休整。

待全部军队骚扰结束并回到自己的城池后。

哈劳斯会下令开始下一轮的骚扰攻击。

卡拉迪亚大陆的人们认为单行道的效率很高，所以卡拉迪亚大陆的道路都是单行道。

现在，你作为卡拉迪亚最最精明的商人马尼德,你十分擅长算计，哈劳斯找到了你，并任命你为辅政大臣，于是这个任务就落到了你的身上。

这个任务就是要计算出并告诉哈劳斯进行一轮骚扰攻击最少要耗费多久时间，因为时间越久，补给要求越高，而哈劳斯是个吝啬鬼。

“哈劳斯？愿他长寿。”,接到任务后你心里想到。

输入格式

第一行 3 个数 n,m,s （其中n为城池总数目，m为道路总数，s 为杰尔喀拉的所在地，其余城池均为斯瓦迪亚的城池）

接下来 m 行，每行 3 个数 u,v,w 表示一条路（其中 u为起点，v为终点，w为行进时间）

以上变量

1 < n < 5000

1 < m < 1e6

1< s <= n

1 < u,v <= n

1< w < 1e6

输出格式

输出一个数 x, 表示最少要耗费的时间。

样例

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

10