Commuter Pass

JOI lives in a city with $N$ stations, numbered from 1 to $N$. The city has $M$ railways, numbered from 1 to $M$. Railway $i$ ($1 \le i \le M$) connects station $A_i$ and station $B_i$ in both directions, and its fare is $C_i$ yen.

JOI lives near station $S$ and attends IOI High School near station $T$. He plans to buy a commuter pass between these two stations. When he buys the pass, he must choose one route between station $S$ and station $T$ whose cost is minimum. With this pass he can ride every railway on the chosen route in either direction at no extra charge.

JOI also often visits bookstores near station $U$ and station $V$. He therefore wants to buy the pass so that the cost of traveling from station $U$ to station $V$ is minimized.

To travel from station $U$ to station $V$, he first chooses a route from station $U$ to station $V$. For each railway $i$ on that route he pays

• 0 yen if railway $i$ is on the route chosen when he bought the pass, or
• $C_i$ yen if railway $i$ is not on the route chosen when he bought the pass.

The sum of these fares is the cost from station $U$ to station $V$.

Write a program that computes the minimum cost from station $U$ to station $V$ when the route for the commuter pass is chosen appropriately.

Read the following data from standard input.

• The first line contains two integers $N$ and $M$ separated by a space. The city JOI lives in has $N$ stations and $M$ railways.
• The second line contains two integers $S$ and $T$ separated by a space. JOI plans to buy a commuter pass between station $S$ and station $T$.
• The third line contains two integers $U$ and $V$ separated by a space. JOI wants to minimize the cost from station $U$ to station $V$.
• The $i$-th of the following $M$ lines ($1 \le i \le M$) contains three integers $A_i$, $B_i$, $C_i$ separated by spaces. Railway $i$ connects station $A_i$ and station $B_i$ in both directions, and its fare is $C_i$ yen.

Print one line to standard output containing the minimum cost from station $U$ to station $V$ when the route for the commuter pass is chosen appropriately.

• $2 \le N \le 100\,000$
• $1 \le M \le 200\,000$
• $1 \le S \le N$
• $1 \le T \le N$
• $1 \le U \le N$
• $1 \le V \le N$
• $S \ne T$
• $U \ne V$
• $S \ne U$ or $T \ne V$
• Every station is reachable from every other station by railways.
• $1 \le A_i < B_i \le N$ ($1 \le i \le M$)
• For every $1 \le i < j \le M$, $A_i \ne A_j$ or $B_i \ne B_j$.
• $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le M$)