题目描述

小A是村里唯一的邮递员，这些年由于现代通讯方式的发展，小A每天要送的信件越来越少，经常几天才要送一次信。

在一个阳光明媚的早上，小A来到邮局，发现今天只要送 $2$ 封信。

小A所在的村子，可以看作一个由 $N$ 个点（点的编号为 $1 \sim N$），$M$ 无向边条边构成的地图。邮局在编号为 $S$ 的位置上，小A在地图上找到了自己今天要送信的两个点 $T_1$ 和 $T_2$。

小A估计，如果他好好规划一下路线，他早上就能送完 $2$ 封信了，于是他准备骑上自己的自行车，开始今天的送信工作。

请你编程帮助小A计算出，他送完这两封信，最少要骑车的公里数。

请注意：你只要计算出，小A送完这两封信，最少要骑车的公里数，不需要考虑小A回来的时间。

输入格式

第 $1$ 行输入 $M, N, S, T_1, T_2$，含义如题所述。

接下来的 $M$ 行，每行输入三个整数 $U_i, V_i, L_i$，表示点 $U_i$ 和 点 $V_i$ 之间存在一条长度为 $L_i$ 的双向道路。

输出格式

输出一个整数，代表小A送完两封信，最少要骑车的公里数。

样例

输入

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

输出

13

数据范围

对于 $30\%$ 的数据，满足 $1 \le M \le 100$，$1 \le N \le 100$。

对于 $100\%$ 的数据，$1 \le M \le 2 \times 10^5$，$1 \le N \le 10^5$，$1 \le U_i, V_i \le N$，$\sum L_i \le 2 \times 10^9$。