1497：农场派对

题目描述

有 $N$ 头牛要去参加一场在编号为 $X$ 的牛的农场举行的派对。有 $M$ 条有向道路，每条路长 $T_i$；每头牛都必须参加完派对后回到家，每头牛都会选择最短路径。求这 $N$ 头牛的最短路径（一个来回）中最长的一条的长度。

特别提醒：可能有权值不同的重边。

输入格式

第一行：$3$ 个整数 $N, M, X$。

接下来 $M$ 行：每行 $3$ 个整数 $A_i, B_i, T_i$，表示有一条从 $A_i$ 到 $B_i$ 的有向道路，长度为 $T_i$。

输出格式

一行一个整数，表示最长最短路的长度。

样例

样例输入 #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

数据范围

• $1 \le N \le 1000$
• $1 \le M \le 100000$
• $1 \le X \le N$
• $1 \le T_i \le 100$

时空限制

• 时间限制：1000 ms
• 内存限制：65536 KB