定期券(Commuter Pass)

JOI 君が住む都市にはN 個の駅があり，それぞれ1, 2, ..., N の番号が付けられている．また，M 本の鉄道路線があり，それぞれ1, 2, ..., 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 への経路を1 つ選ぶ．この経路に含まれる鉄道路線i において支払うべき運賃は，

• 鉄道路線i が定期券を購入する際に指定した経路に含まれる場合，0 円
• 鉄道路線i が定期券を購入する際に指定した経路に含まれない場合，C_i 円

となる．この運賃の合計が，駅U から駅V への移動にかかる運賃である．

定期券を購入する際に指定する経路をうまく選んだときの，駅U から駅V への移動にかかる運賃の最小値を求めたい．

課題

定期券を購入する際に指定する経路をうまく選んだときの，駅U から駅V への移動にかかる運賃の最小値を求めるプログラムを作成せよ．

入力

標準入力から以下の入力を読み込め．

• 1 行目には，2 個の整数N, M が書かれている．これらは，JOI 君が住む都市にN 個の駅とM 本の鉄道路線があることを表す．
• 2 行目には，2 個の整数S, T が書かれている．これらは，JOI 君が駅S から駅T への定期券を購入することを表す．
• 3 行目には，2 個の整数U, V が書かれている．これらは，JOI 君が駅U から駅V への移動にかかる運賃を最小化したいことを表す．
• 続くM 行のうちのi 行目(1 \leq i \leq M) には，3 個の整数A_i, B_i,C_i が書かれている．これらは，鉄道路線i が駅A_i と駅B_i を双方向に結び，その運賃がC_i 円であることを表す．

出力

標準出力に，定期券を購入する際に駅S から駅T への経路をうまく指定したときの，駅U から駅V への移動にかかる運賃の最小値を1 行で出力せよ．

制限

すべての入力データは以下の条件を満たす．

• 2 \leq N \leq 100 000．
• 1 \leq M \leq 200 000．
• 1 \leq S \leq N．
• 1 \leq T \leq N．
• 1 \leq U \leq N．
• 1 \leq V \leq N．
• S ≠ T．
• U ≠ V．
• S ≠ U またはT ≠ V．
• どの駅から他のどの駅へも1 本以上の鉄道路線を用いて到達できる．
• 1 \leq A_i < B_i \leq N (1 \leq i l\leq M)．
• 1 \leq i < j \leq M に対し，A_i ≠ A_j またはB_i ≠ B_j．
• 1 \leq C_i \leq 1 000 000 000 (1 \leq i \leq M)．

入出力例

入力例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 → 駅2 → 駅3 → 駅5 → 駅6 という経路に限られる．

駅1 から駅4 への移動にかかる運賃を最小化するには，駅1 → 駅2 → 駅3 → 駅5 → 駅4 という経路を選べばよい．この経路を選んだ場合，各鉄道路線において支払うべき運賃は，

• 駅4 と駅5 を結ぶ鉄道路線5 においては，2 円．
• それ以外の鉄道路線においては，0 円．

となるので，かかる運賃の合計は2 円となる．

入力例2

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

出力例2

3000000000

この入力例では，駅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

情報オリンピック日本委員会作 『第17 回日本情報オリンピック(JOI 2017/2018) 本選』

---