정기권

JOI 군이 사는 도시에는 역이 $N$개 있다. 역에는 1부터 $N$까지 번호가 붙어 있다. 철도 노선은 $M$개이고, 1부터 $M$까지 번호가 붙어 있다. 노선 $i$ ($1 \le i \le M$)는 역 $A_i$와 역 $B_i$를 양방향으로 잇고, 요금은 $C_i$엔이다.

JOI 군은 역 $S$ 근처에 살고, 역 $T$ 근처에 있는 IOI 고등학교에 다닌다. 그래서 두 역을 잇는 정기권을 사려고 한다. 정기권을 살 때는 역 $S$와 역 $T$ 사이의 경로 중 비용이 최소인 경로를 하나 골라야 한다. 이 정기권이 있으면 고른 경로에 포함된 노선은 어느 방향으로든 추가 요금 없이 탈 수 있다.

JOI 군은 역 $U$와 역 $V$ 근처의 서점에도 자주 간다. 그래서 역 $U$에서 역 $V$까지 가는 비용이 최소가 되도록 정기권을 사고 싶다.

역 $U$에서 역 $V$로 갈 때는 먼저 역 $U$에서 역 $V$까지의 경로를 하나 고른다. 그 경로에 포함된 각 노선 $i$의 요금은 다음과 같다.

• 노선 $i$가 정기권을 살 때 고른 경로에 포함되면 0엔
• 노선 $i$가 정기권을 살 때 고른 경로에 포함되지 않으면 $C_i$엔

이 요금의 합이 역 $U$에서 역 $V$까지의 비용이다.

정기권을 살 때 경로를 알맞게 고른다고 할 때, 역 $U$에서 역 $V$까지의 최소 비용을 구하는 프로그램을 작성하시오.

표준 입력에서 다음 데이터를 읽는다.

• 첫째 줄에 정수 $N$, $M$이 공백으로 구분되어 주어진다. JOI 군이 사는 도시에 역이 $N$개, 철도 노선이 $M$개 있다는 뜻이다.
• 둘째 줄에 정수 $S$, $T$가 공백으로 구분되어 주어진다. JOI 군이 역 $S$와 역 $T$를 잇는 정기권을 사려 한다는 뜻이다.
• 셋째 줄에 정수 $U$, $V$가 공백으로 구분되어 주어진다. JOI 군이 역 $U$에서 역 $V$까지의 비용을 최소로 만들고 싶다는 뜻이다.
• 이어지는 $M$개 줄 중 $i$번째 줄 ($1 \le i \le M$)에 정수 $A_i$, $B_i$, $C_i$가 공백으로 구분되어 주어진다. 노선 $i$가 역 $A_i$와 역 $B_i$를 양방향으로 잇고, 요금이 $C_i$엔이라는 뜻이다.

표준 출력에 한 줄을 출력한다. 정기권을 살 때 경로를 알맞게 골랐을 때 역 $U$에서 역 $V$까지 가는 최소 비용을 출력한다.

• $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$ 또는 $T \ne V$
• 철도를 타면 어느 역에서든 다른 어느 역으로도 갈 수 있다.
• $1 \le A_i < B_i \le N$ ($1 \le i \le M$)
• $1 \le i < j \le M$인 모든 $i$, $j$에 대해 $A_i \ne A_j$ 또는 $B_i \ne B_j$
• $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le M$)