题目描述

给定一张 $n$ 个点的无自环的无向联通图，$m$ 条正权边。第 $i$ 边连接 $u_i$ 和 $v_i$，长度为 $w_i$。

找一条从 $S$ 出发，经过 $T_1$ 和 $T_2$ 的最短路径，不要求先后顺序。

输入格式

第一行包括五个数 $m$，$n$，$S$，$T_1$，$T_2$。

接下来 $m$ 行，每行有三个数 $u_i$，$v_i$，$w_i$。

输出格式

输出一个整数，表示最短路径的长度。

样例输入

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

样例输出

12

数据规模与约定

对于 $100\%$ 的数据，$1\le n\le10^5$，$1\le m\le2\times10^5$，$1\le u_i,v_i\le n$，$1\le w_i\le2\times10^9$，$1\le S,T_1,T_2\le n$。