4362: 「JOI 2018 Final」月票购买

JOI 所住的城市有 $N$ 个车站，分别编号为 $1 \dots N$。有 $M$ 条铁路，编号为 $1 \dots M$。第 $i$ 条铁路双向连接车站 $A_i$ 与车站 $B_i$，乘车费用为 $C_i$。 JOI 住在车站 $S$ 附近，而 JOI 所在的 IOI 高中在车站 $T$ 附近。他打算买一张月票往返这两个车站。当他买这张月票时，他需要选择一条在车站 $S$ 与车站 $T$ 之间的乘车费用最小的路径。有了这张月票，JOI 可以无需额外费用，双向通过任意所选路径包含的铁路。 JOI 经常去在车站 $U$ 与车站 $V$ 附近的书店，因此他希望能买一张月票使得从车站 $U$ 到车站 $V$ 的花费最小。 当他要从车站 $U$ 去往车站 $V$ 时，他会选择一条从车站 $U$ 到车站 $V$ 的路径。对于路径上的每段铁路，如果这段铁路在月票指定的路径范围内，则费用为 $0$，否则费用为 $C_i$。每段铁路的费用和为 JOI 从车站 $U$ 到车站 $V$ 的总费用。 他想要知道，如果他买月票时选择了一条合适的路线，从车站 $U$ 到车站 $V$ 的最小费用是多少。 你需要编写一个程序计算最小费用。

从标准输入中读取数据。 第一行包括两个整数 $N, M$，表示 JOI 所住的城市中车站的数量与铁路的数量。 第二行包括两个整数 $S, T$，表示 JOI 所计划购入的月票的起点与终点。 第三行包括两个整数 $U, V$，表示 JOI 想要最小化从车站 $U$ 到车站 $V$ 的费用。 接下来 $M$ 行，第 $i+3$ 行有三个整数 $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