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

문제

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).

서브태스크

번호 배점 제한
1 16

S = U.

2 15

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

3 24

N ≤ 300.

4 45

There are no additional constraints.

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

채점 및 기타 정보

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