시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 256 MB2141048648.315%

## 문제

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 Ai and the station Bi in both directions, and the fare is Ci yen.

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
• Ci 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.

• 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 Ai, Bi, Ci. The railway i connects the station Ai and the station Bi in both directions, and the fare is Ci 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.

## 제한

• 2 ≤ N ≤ 100 000.
• 1 ≤ M ≤ 200 000.
• 1 ≤ S ≤ N.
• 1 ≤ T ≤ N.
• 1 ≤ U ≤ N.
• 1 ≤ V ≤ N.
• S ≠ T.
• U ≠ V.
• S ≠ U or T ≠ V.
• JOI-kun can move from any stations to any other stations taking railways.
• 1 ≤ Ai < Bi ≤ N (1 ≤ i ≤ M).
• For every 1 ≤ i < j ≤ M, either Ai ≠ Aj or Bi ≠ Bj.
• 1 ≤ Ci ≤ 1 000 000 000 (1 ≤ i ≤ M).

## 서브태스크

번호배점제한
116

S = U.

215

There is a unique route with minimum cost from the station S to the station T.

324

N ≤ 300.

445

## 예제 입력 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


In this sample input, there is only one route JOI-kun can choose when he buys a commuter pass: Station 1 → Station 2 → Station 3 → Station 5 → Station 6.

In order to minimize the cost from the station 1 to the station 4, he chooses the following route: Station 1 → Station 2 → Station 3 → Station 5 → Station 4. When he chooses this route, the fare he has to pay is

• 2 yen for the railway 5 connecting the station 4 and the station 5, and
• 0 yen for other railways.

Hence the total cost is 2 yen.

## 예제 입력 2

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


## 예제 출력 2

3000000000


In this sample input, JOI-kun does not use the commuter pass when he moves from the station 3 to the station 6.

## 예제 입력 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


## 채점 및 기타 정보

• 예제는 채점하지 않는다.