AT_joi2018ho_d 定期券 (Commuter Pass)

[problemUrl]: https://atcoder.jp/contests/joi2018ho/tasks/joi2018ho_d JOI 君が住む都市には $ N $ 個の駅があり，それぞれ $ 1,\ 2,\ \ldots,\ N $ の番号が付けられている．また，$ M $ 本の鉄道路線があり，それぞれ $ 1,\ 2,\ \ldots,\ M $ の番号が付けられている．鉄道路線 $ i $ ($ 1\ \leqq\ i\ \leqq\ 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 $ への移動にかかる運賃の最小値を求めたい．

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

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

### 課題 定期券を購入する際に指定する経路をうまく選んだときの，駅 $ U $ から駅 $ V $ への移動にかかる運賃の最小値を求めるプログラムを作成せよ． - - - - - - ### 制限 すべての入力データは以下の条件を満たす． - $ 2\ \leqq\ N\ \leqq\ 100\,000 $． - $ 1\ \leqq\ M\ \leqq\ 200\,000 $． - $ 1\ \leqq\ S\ \leqq\ N $． - $ 1\ \leqq\ T\ \leqq\ N $． - $ 1\ \leqq\ U\ \leqq\ N $． - $ 1\ \leqq\ V\ \leqq\ N $． - $ S\ \neq\ T $． - $ U\ \neq\ V $． - $ S\ \neq\ U $ または $ T\ \neq\ V $． - どの駅から他のどの駅へも $ 1 $ 本以上の鉄道路線を用いて到達できる． - $ 1\ \leqq\ A_i\