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 A_i and the station B_i 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.

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