题目描述

小猪在森林里迷路了，他想回家。森林中有 $N$ 个地点，编号为 $1$ 到 $N$，其中 $1$ 号地点是小猪的家。

有 $M$ 条小路连接这些地点，每条小路有一定的长度。小猪想找到从当前位置到家的最短路径。

给定小猪当前所在的地点 $S$，请计算从 $S$ 到 $1$ 的最短距离。

输入格式

第一行三个整数 $N, M, S$。

接下来 $M$ 行，每行三个整数 $U, V, W$，表示 $U$ 和 $V$ 之间有一条长度为 $W$ 的小路。

输出格式

输出一个整数，表示从 $S$ 到 $1$ 的最短距离。

样例

输入

5 6 5
1 2 2
1 3 4
2 3 1
2 4 7
3 5 3
4 5 1

输出

6

数据范围

对于 $100\%$ 的数据，满足 $1 \le N \le 10^5$，$1 \le M \le 2 \times 10^5$，$1 \le W \le 10^4$。