题目描述

光头强和他的 $n−1$ 个同学住在同一个小镇上，这个小镇可以看成一张简单有向图，共有 $n$ 个顶点和 $m$ 条边。每一位同学（包括光头强）住在不同的顶点。

现在这些同学周末要到光头强家聚会，光头强家在 $k$ 号顶点，所有同学在聚会完需要回家。为了合理安排时间，光头强想要知道对于在路上来回花费时间最长的同学，他在路上要花费多少时间。

你需要求出在路上来回花费时间最长的同学在路上花费了多少时间。

输入格式

输入第一行输入三个整数 $n,m,k$，表示图的顶点数、边数，以及光头强所在的顶点编号。

接下来 $m$ 行，每行三个整数 $x,y,z$，表示 $x$ 到 $y$ 有一条有向边，通过它需要花费 $z$ 的时间。

输入保证所有点两两连通。

输出格式

输出一个数表示答案。

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

6

数据规模

对于所有数据，保证 $2≤n≤100000,1≤m≤100000,1≤k≤n,1≤x,y≤n,x≠y,1≤z≤10000$。