JOI-kun is living in a city with N stations. The stations are numbered from 1 to N. There are M railways numbered from 1 to M. The railway i (1 ≤ i ≤ M) connects the station A_i and the station B_i in both directions, and the fare is C_i yen.</p>

JOI-kun is living near the station S, and goes to the IOI high school near the station T. He is planning to buy a commuter pass connecting these two stations. When he buys a commuter pass, he needs to choose a route between the station S and the station T with minimum cost. Using this commuter pass, he can take any railways contained in a chosen route in any directions without additional costs.

JOI-kun often goes to bookstores near the station U and the station V. Therefore, he wants to buy a commuter pass so that the cost from the station U to the station V is minimized.

When he moves from the station U to the station V, he first choose a route from the station U to the station V. Then the fare he has to pay is

• 0 yen if the railway i is contained in a route chosen when he buys a commuter pass, or
• C_i yen if the railway i is not contained in a route chosen when he buys a commuter pass.

The sum of the above fare is the cost from the station U to the station V.

He wants to know the minimum cost from the station U to the station V if he chooses a route appropriately when he buys a commuter pass.

Write a program which calculates the minimum cost from the station U to the station V if he chooses a route appropriately when he buys a commuter pass.

입력 형식

Read the following data from the standard input.</p>

• The first line of input contains two space separated integers N, M. This means the city JOI-kun lives in has N stations and M railways.
• The second line contains two space separated integers S, T. This means JOI-kun is planning to buy a commuter pass from the station S to the station T.
• The third line contains two space separated integers U, V. This means JOI-kun wants to minimize the cost from the station U to the station V.
• The i-th line (1 ≤ i ≤ M) of the following M lines contains three space separated integers A_i, B_i, C_i. The railway i connects the station A_i and the station B_i in both directions, and the fare is C_i yen.

Write one line to the standard output. The output should contain the minimum cost from the station U to the station V if he chooses a route appropriately when he buys a commuter pass.

예제 입력 1

6 6
1 6
1 4
1 2 1
2 3 1
3 5 1
2 4 3
4 5 2
5 6 1

예제 출력 1

2

예제 입력 2

6 5
1 2
3 6
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000

예제 출력 2

3000000000

예제 입력 3

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

예제 출력 3

15

예제 입력 4

5 5
1 5
2 3
1 2 1
2 3 10
2 4 10
3 5 10
4 5 10

예제 출력 4

0

예제 입력 5

10 15
6 8
7 9
2 7 12
8 10 17
1 3 1
3 8 14
5 7 15
2 3 7
1 10 14
3 6 12
1 5 10
8 9 1
2 9 7
1 4 1
1 8 1
2 4 7
5 6 16

예제 출력 5

19