题目描述

华莱市一共有$N$（$N \leq 5000$）个城市，城市之间有$M$（$M \leq 30000$）条双向道路相连。这些城市两两之间都可以通过一些道路到达，通过城市$A_i$和$B_i$间的道路会产生$P_i$的耗时。 $2020$年金融危机，一逃犯做生意破产跑路了，小$D$现在要抓补这名逃犯。经大数据分析逃犯最有可能从$1$号城市跑路到$N$号城市，但他有一个特别喜欢的$GF$，中途可能会停留在$GF$家，而$GF$在$K$号城市，所以小$D$抓捕逃犯的路线即为$1--K--N$。小$D$若想追上逃犯，必须抓紧一切时间，你能帮助小$D$计算出逃跑路线需要花费的最少时间么？

输入格式

第一行三个正整数$N$、$M$、$K$，含义如题面所述。 接下来$M$行，每行三个正整数$X_i$、$Y_i$、$P_i$，表示一条连接$X_i$和$Y_i$的双向道路，途径需要$P_i$的时间。可能有自环，可能有重边。$1 \leq P_i\leq 1000$。

输出格式

输出一个正整数，表示从城市$1$到城市$K$，再从城市$K$到城市$N$，即$1--K--N$，总耗时最短为多少。

样例

样例输入

7 10 4
1 3 10
2 6 9
4 1 5
3 7 4
3 6 9
1 5 8
2 7 4
3 2 10
1 7 6
7 6 9

样例输出

16

数据范围与提示

对于$20$的数据，$N \leq 30$,$M \leq 100$

对于$40$的数据，$N \leq 300$,$M \leq 1000$

对于$100$的数据，$N \leq 5000$,$M \leq 30000$. $P_i \leq 1000$.