시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 12 6 6 100.000%

문제

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.

All input data satisfy the following conditions.

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

출력

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

힌트

In this sample input 1, 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.

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