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 \le i \le 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 railway contained in a chosen route in any direction 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 chooses 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.

Input Specification

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~ (~S \neq 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~ (~U \neq V~). This means JOI-kun wants to minimize the cost from the station ~U~ to the station ~V~.

Each of the following ~M~ lines contains three space separated integers ~A_i~, ~B_i~, ~C_i~ (~1 \le A_i, B_i \le N~, ~1 \le C_i \le 10^9~). The railway ~i~ connects the station ~A_i~ and the station ~B_i~ in both directions, and the fare is ~C_i~ yen.

Output Specification

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.

Constraints

In all test cases, ~1 \le N \le 10^5~, ~1 \le M \le 2 \times 10^5~, ~S \neq U~ or ~T \neq V~.

In ~16\%~ test cases, ~S = U~.

In another ~15\%~ test cases, there is a unique route with minimum cost from the station ~S~ to the station ~T~.

In another ~24\%~ test cases, ~N \le 300~.

Sample Input 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

Sample Output 1

2

Sample Input 2

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

Sample Output 2

15