题目描述

JOI 君住在一个有 $N$ 个车站的城市。车站编号为 $1$ 至$N$。编号为 $1$ 至 $M$ 的有 $M$ 条铁路。铁路 $i$（$1 \leq i \leq M$）双向连接 $A_i$ 站和 $B_i$ 站，票价为 $C_i$ 日元。
JOI 君住在 $S$ 站附近，去 $T$ 站附近的 IOI 高中。他打算买一张连接这两个站的通勤票。当他购买通勤票时，他需要选择一条成本最低的 $S$ 站和 $T$ 站之间的路线。使用此通勤票，他可以沿任何方向乘坐所选路线中包含的任何铁路，而无需额外费用。
JOI 君经常去 $U$ 站和 $V$ 站附近的书店。因此，他想买一张通勤票，这样从 $U$ 站到 $V$ 站的费用可以降到最低。
当他从 $U$ 站移动到 $V$ 站时，他首先选择了一条从 $U$ 站到 $V$ 站的路线，那么他需要支付的车费是：

• $0$ 日元：如果铁路 $i$ 包含在他购买的通勤票时选择的路线中，或者，
• $C_i$ 日元：如果铁路 $i$ 不包含在他购买通勤票时选择的路线中。

上述票价的总和就是从 $U$ 站到 $V$ 站的成本。
他想知道如果他在购买通勤票时选择合适的路线，从 $U$ 站到 $V$ 站的最低成本。

输入格式

第一行包含两个空格分隔的整数 $N$，$M$。这意味着 JOI 君居住的城市有 $N$ 个车站和 $M$ 条铁路。第二行包含两个空格分隔的整数 $S$，$T$。这意味着 JOI 君计划购买从 $S$ 站到 $T$ 站的通勤票。第三行包含两个空格分隔的整数 $U$，$V$。这意味着 JOI 君想要最小化从站 $U$ 到站 $V$ 的成本。接下来的 $M$ 行的第 $i$ 行包含三个空格分隔的整数 $A_i$，$B_i$，$C_i$。铁路 $i$ 双向连接 $A_i$ 站和 $B_i$ 站，票价为 $C_i$ 日元。

输出格式

如果他在购买通勤票时选择了适当的路线，则输出应包含一个整数为从站 $U$ 到站 $V$ 的最小成本。

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

2

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

3000000000

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

15

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

0

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

19

提示

数据规模与约定

对于 $100 \%$ 的数据，
$2 \leq N \leq 10^5$，$1 \leq M \leq 2×10^5$，$1 \leq S \leq N$，$1 \leq T \leq N$，$1 \leq U \leq N$，$1 \leq V \leq N$，$S {=}\mathllap{/\,} T$，$U {=}\mathllap{/\,} V$，$S{=}\mathllap{/\,} U$ 或 $T {=}\mathllap{/\,} V$，$1 \leq A_i \leq B_i \leq N$（$1 \leq i \leq M$）。对于每 $1 \leq i < j \leq M$，$A_i {=}\mathllap{/\,} A_j$ 或 $B_i {=}\mathllap{/\,} B_j$，$1 \leq C_i \leq 10^9$（$1 \leq i \leq M$）。JOI 君可以从任何车站移动到任何其他车站乘坐铁路。

• Subtask $1$（$16$ points）：$S=U$。
• Subtask $2$（$15$ points）：从 $S$ 站到 $T$ 站有一条成本最低的唯一路线。
• Subtask $3$（$24$ points）：$N \leq 300$。
• Subtask $4$（$45$ points）：没有额外的限制。

样例说明

对于样例 $1$：JOI 君在购买通勤票时只能选择一条路线：$1$ 号站 → $2$ 号站 →$3$ 号站 → $5$ 号站 → $6$ 号站。为了尽量减少从 $1$ 号站到 $4$ 号站的成本 ，他选择以下路线：$1$ 站 → $2$ 站 → $3$ 站 → $5$ 站 → $4$ 站。选择这条路线时，他需要支付的车费为。

• $2$ 日元用于车站 $4$ 和车站 $5$ 的铁路 $5$，以及，
• $0$ 日元：其他铁路。

对于样例 $2$：JOI 君从 $3$ 号站移动到 $6$ 号站时，不使用通勤票。

题目说明：

来源于 The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Final Round 的 T4：Commuter Pass。
由 @求学的企鹅 翻译整理。

Hack 说明

@gaojunqing 于 2021 年 11 月 6 日向供题人提供一组 hack 数据，经过多次检验后于 2021 年 11 月 7 日加入到本题测试数据中。
出于对该 JOI 原题的尊重与体验考虑，一律所加入的 hack 数据均不做分值改变，即满分依然为 100 分，新增 hack 数据单独放置在 Subtask #5 ，且分数为 0 分。即如通过原所有测试数据而未通过 hack 数据，将获得 100 分但不能 AC，当且仅当通过全部测试数据方可 AC。