15556번 - Commuter Pass 출처다국어분류

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

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

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 ≤ A_i < B_i ≤ N (1 ≤ i ≤ M).
• For every 1 ≤ i < j ≤ M, either A_i ≠ A_j or B_i ≠ B_j.
• 1 ≤ C_i ≤ 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.

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.