Problem Description

In the city where JOI lives, there are $ N $ stations numbered $1, 2, \ldots, N$. There are also $ M $ railway lines numbered $1, 2, \ldots, M$. Railway line $ i $ ($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 $. Therefore, he decided to purchase a commuter pass connecting both. When purchasing a commuter pass, one must specify a route with the minimum fare between station $ S $ and station $ T $. With this commuter pass, one can freely board and alight the railway lines included in the specified route in both directions.

JOI also frequently uses a bookstore near station $ U $ and station $ V $. Thus, he wants to purchase a commuter pass such that the fare for traveling from station $ U $ to station $ V $ is minimized.

When traveling from station $ U $ to station $ V $, one first selects a route from station $ U $ to station $ V $. For each railway line $ i $ included in this route, the fare to be paid is:

• $ 0 $ yen if railway line $ i $ is included in the route specified for the commuter pass,
• $ C_i $ yen if railway line $ i $ is not included in the route specified for the commuter pass.

The total fare is the sum of the fares for all railway lines in the selected route. We want to find the minimum fare for traveling from station $ U $ to station $ V $ when the route for the commuter pass is optimally chosen.

Input Format

Read the following input from standard input:

• The first line contains two integers $ N $ and $ M $, indicating that there are $ N $ stations and $ M $ railway lines in the city where JOI lives.
• The second line contains two integers $ S $ and $ T $, indicating that JOI will purchase a commuter pass from station $ S $ to station $ T $.
• The third line contains two integers $ U $ and $ V $, indicating that JOI wants to minimize the fare for traveling from station $ U $ to station $ V $.
• The next $ M $ lines contain three integers $ A_i $, $ B_i $, and $ C_i $ each, indicating that railway line $ i $ connects station $ A_i $ and station $ B_i $ bidirectionally with a fare of $ C_i $ yen.

Output Format

Output to standard output the minimum fare for traveling from station $ U $ to station $ V $ when the route for the commuter pass is optimally chosen, on a single line.

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

Task

Write a program to find the minimum fare for traveling from station $ U $ to station $ V $ when the route for the commuter pass is optimally chosen.

Constraints

All input data satisfies the following conditions:

• $2 \leq N \leq 100,000$.
• $1 \leq M \leq 200,000$.
• $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$.
• Any station can be reached from any other station using one or more railway lines.
• $1 \leq A_i < B_i \leq N$ ($1 \leq i \leq M$).
• For $1 \leq i < j \leq M$, $A_i \neq A_j$ or $B_i \neq B_j$.
• $1 \leq C_i \leq 1,000,000,000$ ($1 \leq i \leq M$).

Subtasks

Subtask 1 [16 points]

• $ S = U $.

Subtask 2 [15 points]

• There is only one route with the minimum fare from station $ S $ to station $ T $.

Subtask 3 [24 points]

• $N \leq 300$.

Subtask 4 [45 points]

• No additional constraints.

Sample Explanation 1

In this input example, the only route available for the commuter pass is station $ 1 $ → station $ 2 $ → station $ 3 $ → station $ 5 $ → station $ 6 $. To minimize the fare for traveling from station $ 1 $ to station $ 4 $, one should choose the route station $ 1 $ → station $ 2 $ → station $ 3 $ → station $ 5 $ → station $ 4 $. For this route, the fare to be paid is:

• $ 2 $ yen for the railway line connecting station $ 4 $ and station $ 5 $,
• $ 0 $ yen for the other railway lines.

Thus, the total fare is $ 2 $ yen.

Sample Explanation 2

In this input example, the commuter pass is not used for traveling from station $ 3 $ to station $ 6 $.

Sample Explanation 3

Sample Explanation 4

见题面 Input 部分

见题面 Output 部分