Problem Description

JOI lives in a city with $N$ stations numbered from $1$ to $N$. There are $M$ railways numbered from $1$ to $M$. Railway $i$ (for $1 \leq i \leq M$) connects station $A_i$ and station $B_i$ bidirectionally with a fare of $C_i$ yen.
JOI lives near station $S$ and goes to IOI High School near station $T$. He plans to buy a commuter pass connecting these two stations. When purchasing the commuter pass, he needs to choose the route with the lowest cost between station $S$ and station $T$. Using this commuter pass, he can travel on any railway included in the chosen route in either direction without additional charges.
JOI often visits a bookstore near station $U$ and station $V$. Therefore, he wants to buy a commuter pass that minimizes the cost from station $U$ to station $V$.
When moving from station $U$ to station $V$, he first chooses a route from station $U$ to station $V$. The fare he needs to pay is:
- $0$ yen if railway $i$ is included in the route chosen for the commuter pass, or
- $C_i$ yen if railway $i$ is not included in the route chosen for the commuter pass.

The sum of these fares is the cost from station $U$ to station $V$.
He wants to know the minimum cost from station $U$ to station $V$ if he chooses the appropriate route when buying the commuter pass.

Input Format

The first line contains two space-separated integers $N$ and $M$, indicating that the city has $N$ stations and $M$ railways. The second line contains two space-separated integers $S$ and $T$, indicating that JOI plans to buy a commuter pass from station $S$ to station $T$. The third line contains two space-separated integers $U$ and $V$, indicating that JOI wants to minimize the cost from station $U$ to station $V$. The next $M$ lines, the $i$-th line contains three space-separated integers $A_i$, $B_i$, and $C_i$, indicating that railway $i$ connects station $A_i$ and station $B_i$ with a fare of $C_i$ yen.

Output Format

Output a single integer, the minimum cost from station $U$ to station $V$ if he chooses the appropriate route when buying the commuter pass.

Sample Input and Output

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

6 5
1 2
3 6
1 2 1000000000 
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000

Sample Output #2

3000000000

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

Sample Output #3

15

Sample Input #4

5 5
1 5
2 3
1 2 1
2 3 10
2 4 10
3 5 10
4 5 10

Sample Output #4

0

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

Sample Output #5

19

Notes/Hints

Data Constraints

For $100\%$ of the data,
$2 \leq N \leq 10^5$, $1 \leq M \leq 2 \times 10^5$, $1 \leq S \leq N$, $1 \leq T \leq N$, $1 \leq U \leq N$, $1 \leq V \leq N$, $S \neq T$, $U \neq V$, $S \neq U$ or $T \neq V$, $1 \leq A_i \leq B_i \leq N$ ($1 \leq i \leq M$). For each $1 \leq i < j \leq M$, $A_i \neq A_j$ or $B_i \neq B_j$, $1 \leq C_i \leq 10^9$ ($1 \leq i \leq M$). JOI can travel from any station to any other station using the railways.
- Subtask $1$ ($16$ points): $S = U$.
- Subtask $2$ ($15$ points): There is a unique route with the lowest cost from station $S$ to station $T$.
- Subtask $3$ ($24$ points): $N \leq 300$.
- Subtask $4$ ($45$ points): No additional constraints.

Sample Explanation

For Sample #1: JOI can only choose one route when buying the commuter pass: station $1$ → station $2$ → station $3$ → station $5$ → station $6$. To minimize the cost from station $1$ to station $4$, he chooses the following route: station $1$ → station $2$ → station $3$ → station $5$ → station $4$. The fare he needs to pay is:
- $2$ yen for railway $5$ between station $4$ and station $5$, and
- $0$ yen for other railways.

For Sample #2: JOI does not use the commuter pass when moving from station $3$ to station $6$.

见题面 Input 部分

见题面 Output 部分