题目描述

村庄的地图由 $N$ 个地点和 $M$ 条双向道路组成。邮局位于地点 $S$，两封信分别需要送到地点 $T_1$ 和地点 $T_2$。

邮递员从地点 $S$ 出发，需要到达 $T_1$ 和 $T_2$，送完信后不必返回邮局。求他需要经过的最短路程。

输入格式

第一行包含五个整数 $M,N,S,T_1,T_2$。

接下来 $M$ 行，每行包含三个整数 $U_i,V_i,L_i$，表示地点 $U_i$ 与地点 $V_i$ 之间有一条长度为 $L_i$ 的双向道路。

输出格式

输出一个整数，表示送完两封信需要经过的最短路程。

5 4 1 3 4
1 2 2
2 3 3
1 3 10
2 4 4
3 4 1

6

样例解释

可以依次经过地点 $1,2,3,4$，总路程为 $2+3+1=6$。

数据范围与提示

• 对于 $30\%$ 的数据，$1 \le M,N \le 100$
• 对于全部数据，$1 \le M \le 2 \times 10^5$，$1 \le N \le 10^5$
• $1 \le S,T_1,T_2,U_i,V_i \le N$
• $L_i$ 为正整数，且所有道路长度之和不超过 $2 \times 10^9$
• 保证两封信都可以送达