bzoj#P2100. [USACO2010 Dec]Apple Delivery

[USACO2010 Dec]Apple Delivery

题目描述

给定一张 nn 个点的无自环的无向联通图,mm 条正权边。第 ii 边连接 uiu_iviv_i,长度为 wiw_i

找一条从 SS 出发,经过 T1T_1T2T_2 的最短路径,不要求先后顺序。

输入格式

第一行包括五个数 mmnnSST1T_1T2T_2

接下来 mm 行,每行有三个数 uiu_iviv_iwiw_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%100\% 的数据,1n1051\le n\le10^51m2×1051\le m\le2\times10^51ui,vin1\le u_i,v_i\le n1wi2×1091\le w_i\le2\times10^91S,T1,T2n1\le S,T_1,T_2\le n