#2350. 「JOI 2018 Final」月票购买

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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 的最小费用。

样例

样例输入 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 唯一能选择的购买月票的路径的车站编号为: 1→2→3→5→6

为了最小化费用,JOI 选择的路径的车站编号为: 1→2→3→5→4 ,他只需要花费 2 单位代价用于从车站 4 中转到车站 5 ,其余铁路无费用。

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

数据范围与提示

Subtask # 分值 特殊条件
1 16 S=U
2 15 S T 乘车费用最小的路径上有且仅有一条边
3 24 N \le 300
4 45 -

对于所有输入数据,有 2≤N≤100000, 1≤M≤200000, 1≤C_i≤10^9
保证 1≤S, T, U, V≤N, S≠T, U≠V S≠U T≠V 1≤A_i<B_i≤N ,图中无重边。