提示: 欢迎访问OurACM平台。
Problem 2243 Daxia like uber

Accept: 41    Submit: 106
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

daxia兼职开uber,现在接到一个两人拼车单.已知如下信息:

1. 地图上共有n个点,m条有向行驶通道.

2. daxia位于点s;

3. 客人一位于点x1,目的地为y1;

4. 客人二位于点x2,目的地为y2.

请帮daxia计算送完两个乘客的最短行驶路程.

Input

测试包含多组数据,每组数据第一行包含两个整数:n(1<=n<=1000),m(1<=m<=100000).

第二行包含五个整数:s,x1,y1,x2,y2(1<=s,x1,y1,x2,y2<=n).

接下来包含m行,每行三个整数:u,v,d(1<=u,v<=n,1<=d<=100).

Output

每组数据输出一行一个整数表示送完两个乘客的最短行驶路程,数据保证肯定能送到.

Sample Input

4 8 4 1 2 2 3 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3

Sample Output

11

Hint

样例接送路线:(4)->2->(1)->(2)->1->(3)

Source

FOJ有奖月赛-2016年8月(daxia专场之过四题方有奖)

Submit  Back  Status  Discuss