题目描述

给出 $n$ 个点 $m$ 条带权边的无向图，小明有两个苹果，一个需送到点 $a$，一个需送到点 $b$，小明从点 $st$ 出发 ，求送完两个苹果所走的最短距离（到达顺序不分先后）。

例如下图，$st=5 ，a=1， b=4$：

               3        2       2
           [1]-----[2]------[3]-----[4]
             \     / \              /
             7\   /4  \3           /2
               \ /     \          /
               [5]-----[6]------[7]
                    1       2

最短路径为：$5 -> 6-> 7 -> 4* -> 3 -> 2 -> 1*$

最短距离为： $12$

输入格式

第一行五个整数：$m \ n \ st \ a \ b( 1 \le m \le 2 \times 10^5 , 1 \le n \le 10^5, 1 \le st , a , b \le n)$

下来 $m$ 行，每行三个非负整数 $x \ y \ w$ ，表示一条连接点 $x$ 和点 $y$ ，边权为 $w$ 的无向边。 所有距离之和不大于 $2 \times 10^9$ 。

输出格式

一行一个整数，表示从点 $st$ 出发 达到点 $a$ 和点 $b$（到达顺序不分先后）的最短距离。

输入输出样例 #1

输入 #1

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

输出 #1

12