JOI-kun 居住在一个有 $N$ 个车站的城市中。车站编号为 $1$ 到 $N$。共有 $M$ 条铁路，编号为 $1$ 到 $M$。铁路 $i$ ($1 \le i \le M$) 连接车站 $A_i$ 和车站 $B_i$，双向通行，票价为 $C_i$ 日元。

JOI-kun 住在车站 $S$ 附近，并前往车站 $T$ 附近的 IOI 高中。他计划购买一张连接这两个车站的通勤月票。当他购买通勤月票时，他需要选择一条从车站 $S$ 到车站 $T$ 的路径，且该路径的成本最小。使用这张通勤月票，他可以免费乘坐所选路径中包含的任何铁路（双向均可）。

JOI-kun 经常去车站 $U$ 和车站 $V$ 附近的书店。因此，他希望购买一张通勤月票，使得从车站 $U$ 到车站 $V$ 的成本最小化。

当他从车站 $U$ 移动到车站 $V$ 时，他首先选择一条从车站 $U$ 到车站 $V$ 的路径。此时他需要支付的费用为： 如果铁路 $i$ 包含在他购买通勤月票时所选的路径中，则费用为 $0$ 日元； 如果铁路 $i$ 不包含在他购买通勤月票时所选的路径中，则费用为 $C_i$ 日元。

上述费用的总和即为从车站 $U$ 到车站 $V$ 的成本。

他想知道，如果他在购买通勤月票时适当地选择路径，从车站 $U$ 到车站 $V$ 的最小成本是多少。

输入格式

从标准输入读取以下数据：

• 第一行包含两个空格分隔的整数 $N, M$。这表示 JOI-kun 居住的城市有 $N$ 个车站和 $M$ 条铁路。
• 第二行包含两个空格分隔的整数 $S, T$。这表示 JOI-kun 计划购买从车站 $S$ 到车站 $T$ 的通勤月票。
• 第三行包含两个空格分隔的整数 $U, V$。这表示 JOI-kun 希望最小化从车站 $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 \neq T$ $U \neq V$ $S \neq U$ 或 $T \neq V$ JOI-kun 可以通过铁路从任何车站到达任何其他车站。 $1 \le A_i < B_i \le N$ ($1 \le i \le M$) 对于每一对 $1 \le i < j \le M$，满足 $A_i \neq A_j$ 或 $B_i \neq B_j$。 * $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le M$)

子任务

子任务 1 [16 分] * $S = U$

子任务 2 [15 分] * 从车站 $S$ 到车站 $T$ 的最小成本路径是唯一的。

子任务 3 [24 分] * $N \le 300$

子任务 4 [45 分] * 无附加限制。

样例

样例输入 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

样例输出 1

2

说明 1

在此样例输入中，JOI-kun 购买通勤月票时只有一条路径可选：车站 $1 \to$ 车站 $2 \to$ 车站 $3 \to$ 车站 $5 \to$ 车站 $6$。 为了最小化从车站 $1$ 到车站 $4$ 的成本，他选择了以下路径：车站 $1 \to$ 车站 $2 \to$ 车站 $3 \to$ 车站 $5 \to$ 车站 $4$。当他选择这条路径时，他需要支付的费用为： 连接车站 $4$ 和车站 $5$ 的铁路 $5$ 需要 $2$ 日元， 其他铁路需要 $0$ 日元。 因此总成本为 $2$ 日元。

样例输入 2

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

样例输出 2

3000000000

说明 2

在此样例输入中，JOI-kun 在从车站 $3$ 移动到车站 $6$ 时没有使用通勤月票。

样例输入 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

样例输出 3

15

样例输入 4

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

样例输出 4

0

样例输入 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

样例输出 5

19