编号为 $1..N$ 的 $N$ 座农场（$1 \le N \le 1000$）各有一头奶牛要去农场 $X$（$1 \le X \le N$）参加盛大的奶牛派对。共有 $M$ 条（$1 \le M \le 100,000$）单向道路连接农场对；经过道路 $i$ 需要 $T_i$（$1 \le T_i \le 100$）个时间单位。

每头奶牛都必须步行去参加派对，并在派对结束后返回自己的农场。每头奶牛都很懒，因此会选择耗时最短的最优路线。由于道路是单向的，返程路线可能与前往派对的路线不同。

在所有奶牛中，步行去参加派对再返回所需的最长时间是多少？

输入格式

从标准输入读取输入。

• 第 1 行：三个用空格分隔的整数，依次为 $N$、$M$ 和 $X$。

第 $2..M+1$ 行：第 $i+1$ 行用三个空格分隔的整数 $A_i$、$B_i$ 和 $T_i$ 描述道路 $i$。这条道路从农场 $A_i$ 通向农场 $B_i$，经过它需要 $T_i$ 个时间单位。

输出格式

将输出写入标准输出。

• 第 1 行：一个整数，即任意一头奶牛必须步行的时间的最大值。

样例

输入格式 1

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

输出格式 1

10

说明

奶牛 $4$ 直接前往派对（$3$ 个时间单位），再经农场 $1$ 和 $3$ 返回（$7$ 个时间单位），总共需要 $10$ 个时间单位。

题目来源：USACO 2007 February Silver