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