题目描述

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

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

数据范围与提示

对于所有输入数据，有 $2 \le N \le 100000, 1 \le M \le 200000, 1 \le C_i \le {10}^9$。
保证 $1 \le S, T, U, V \le N, S \ne T, U \ne V$，$S \ne U$ 或 $T \ne V$，$1 \le A_i < B_i \le N$，图中无重边。