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\ne 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\ne 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\ne U$ or $T\ne V$.

In $16\mathrm{\%}$ test cases, $S=U$.

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

In another $24\mathrm{\%}$ 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