AT_joi2021ho_d ロボット (Robot)

[problemUrl]: https://atcoder.jp/contests/joi2021ho/tasks/joi2021ho_d IOI 町には $ N $ 個の交差点があり，$ 1 $ から $ N $ までの番号が付いている．また，$ M $ 本の道があり，$ 1 $ から $ M $ までの番号が付いている．それぞれの道は $ 2 $ 個の異なる交差点を双方向に結んでいる．道 $ i $ ($ 1\ \leqq\ i\ \leqq\ M $) は交差点 $ A_i $ と交差点 $ B_i $ を結んでいる．$ 2 $ 本の異なる道が同じ交差点の組を結ぶことはない．これらの道には $ 1 $ 以上 $ M $ 以下の整数で表される色が塗られており，道 $ i $ の現在の色は $ C_i $ である．複数の道が同じ色で塗られているかもしれない． JOI 社は IOI 町の交差点を移動するロボットを開発した．あなたがこのロボットに道の色を指示すると，ロボットは指示された色の道を通り隣接した交差点に移動する．ただし，ロボットが現在いる交差点につながれた道のうちに，指示された色の道が $ 2 $ 本以上存在すると，次に進むべき道を判別できずに停止してしまう． あなたの目的は，現在交差点 $ 1 $ にいるロボットに何回かの指示を出して，交差点 $ N $ に移動させることである．ただし，現在の道の色ではそれができるとは限らないため，何本かの道の色を**事前に**塗り替えることで， ロボットを交差点 $ N $ に移動させることができるようにしたい．道 $ i $ ($ 1\ \leqq\ i\ \leqq\ M $) は $ P_i $ 円をかけて，$ 1 $ 以上 $ M $ 以下の好きな整数の色に塗り替えることが出来る． 交差点と道の情報が与えられたとき，必要な金額の最小値を求めるプログラムを作成せよ．ただし，どのように道の色を塗り替えてもロボットを交差点 $ N $ に移動させることができない場合は，代わりに `-1` を出力せよ． - - - - - -

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である． > $ N $ $ M $ $ A_1 $ $ B_1 $ $ C_1 $ $ P_1 $ $ \vdots $ $ A_M $ $ B_M $ $ C_M $ $ P_M $

標準出力に必要な金額の最小値を $ 1 $ 行で出力せよ．ただし，どのように道の色を塗り替えてもロボットを交差点 $ N $ に移動させることができない場合は，代わりに `-1` を出力せよ． - - - - - -

### 制約 - $ 2\ \leqq\ N\ \leqq\ 100\,000 $． - $ 1\ \leqq\ M\ \leqq\ 200\,000 $． - $ 1\ \leqq\ A_i\