Problem Description

bilibili拜年祭上，小妹妹被邪♂恶的组织带♂走的事情，引发了 22 和 33 的关注。

小妹妹被带到了从 22 和 33 所在地区出发最危♂险的地区。

22需要尽可能快地赶到小妹妹被带♂去的地点，来保护 knows nothing about *♂* 的小妹妹。

总路程的危险值是叠加的，也就是说 22 每经过一条路，她的路程的危险值就要加上该道路的危险值。

Input

第一行有 $n , m , s$ 三个正整数 ( $1 \lt n \leq 100000$ , $m \leq 200000 , 0 \lt s \leq n$ ) 表示邪♂恶组织地盘数和道路数以及 22 的出发地

接下来的 $m$ 行，每行有 $3$ 个正整数 $a , b , c$ ( $a,b \leq n , 0 \lt c \leq 100000$ )

$a，b$ 表示道路所连通的地区，$c$ 表示该道路危险值，越大代表越危险

由于邪♂恶组织道路比较邪♂恶，所以只能保证道路可以使任意两城市互达（道路是无向的）

Output

输出一个正整数，表示 22 到达小妹妹所在区域所经历的总危险值的最小值

Sample Input

2 1 1
1 2 233

Sample Output

233