题目描述

寒假到了，$n$ 头牛都要去参加一场在编号为 $x$ 的牛的农场举行的派对，农场之间有 $m$ 条有向路，每条路都有一定的长度。

每头牛参加完派对后都必须回家，无论是去参加派对还是回家，每头牛都会选择最短路径，求这 $n$ 头牛的最短路径（一个来回）中最长的一条路径长度。

输入格式

第一行有三个整数，分别表示牛的数量 $n$，道路数 $m$ 和派对农场编号 $x$。 接下来 $m$ 行，每行三个整数 $u, v, w$，表示存在一条由 $u$ 通向 $v$ 的长度为 $w$ 的道路。

输出格式

输出一行一个整数表示答案。

数据范围与约定

对于全部的测试点，保证 $1 \leq x \leq n \leq 10^3$，$1 \leq m \leq 10^5$，$1 \leq u,v \leq n$，$1 \leq w \leq 10^2$，保证从任何一个结点出发都能到达 $x$ 号结点，且从 $x$ 出发可以到达其他所有节点。

可见测试数据

输入数据 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

输入数据 2

5 8 2
1 2 6
2 3 3
3 4 17
4 5 20
5 1 8
3 1 3
3 5 1
2 1 25

输出数据 2

54

输入数据 3

6 11 3
1 2 11
2 3 17
3 4 1
4 5 9
5 6 16
6 1 17
4 6 19
6 2 13
6 3 4
2 5 22
6 1 30

输出数据 3

65