月票购买
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 32 M，其他语言64 M
64bit IO Format: %lld

题目描述

JOI所住的城市有N个车站，分别编号为。有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

输出

复制 
2

说明

样例中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

输出

复制 
3000000000

说明

在这个样例中，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

输出

复制 
15
示例4

输入

复制 
5 5
1 5
2 3
1 2 1
2 3 10
2 4 10
3 5 10
4 5 10

输出

复制 
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

输出

复制 
19

备注:

对于所有输入数据，有。
保证1≤S,T,U,V≤N,S≠T,U≠V，S≠U或T≠V，，图中无重边。

 CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/2350