Description

小z想去A星球旅游。A星球上有多个城市，且城市之间由无向边相连通。小A会先到达 $1$ 号城市，再从 $n$ 号城市返回地球。他听说 $k$ 号城市一定要去。所以他准备从 $1$ 到 $k$ 再到 $n$。但他中途不想经过同一个城市$2$次。

他同样希望在路上的时间要尽可能短。求最短旅游时间（假设在城市不花时间）。

Input Format

从文件 tour.in 读入数据

输入的第一行是三个正整数 $n, m, k$，分别表示城市数,边数和必须要去的城市。

接下来 $m$ 行，每行包含 $3$ 个整数 $u_i,v_i,z_i$ 分别表示边的两个端点和经过这条边所需要的时间。

Output Format

向文件 tour.out 输出数据

输出一行，表示最短时间。若无法满足条件，则输出 -1 .

Sample

样例输入1

4 5 2
1 2 7
2 3 1
1 3 3
3 4 5
2 4 8

样例输出1

12

Hint

$30\%$ : $n \le 10, m \le 30$

$50\%$ : $n \le 20, m \le 100$

$100\%$ : $n \le 10000, m \le 100000$

$z_i \le 10000$