Assuming that you are playing a video game Mirror’s Edge. Mirror’s Edge is a parkour game, in which you are required to move your role around the map to convey secret information. The map will be described by n areas and m two-way paths that connect two different areas. At the very beginning of the game, you are in area 1 and then you need to arrive area a,b,c,d,e, but no order is required. Undoubtedly, you would like to find the fastest path.
The first line contains two integers n and m. The second line contains five integer a,b,c,d,e. The next m lines, each line describes a path. Each line contains three integers x,y,t, indicating this line connect area x and area y and it will cost t seconds to pass it.
A integer t indicates possible shortest time.
1≤n≤500000,1≤m≤1000000;
1<a,b,c,d,e≤n;
1≤x,y≤n,1≤t≤100;
6 6 2 3 4 5 6 1 2 8 2 3 3 3 4 4 4 5 5 5 6 2 1 6 7
21