AT_joi2020ho_d オリンピックバス (Olympic Bus)

[problemUrl]: https://atcoder.jp/contests/joi2020ho/tasks/joi2020ho_d JOI 国には $ N $ 個の都市があり，$ 1 $ から $ N $ までの番号が付いている．また，都市と都市を一方向に結ぶ $ M $ 本のバス路線があり，$ 1 $ から $ M $ までの番号が付いている．バス路線 $ i $ ($ 1\ \leqq\ i\ \leqq\ M $) は都市 $ U_i $ から都市 $ V_i $ へ向けて運行されており，運賃は $ C_i $ 円である．バス路線 $ i $ ($ 1\ \leqq\ i\ \leqq\ M $) では，都市 $ U_i $ 以外で乗ったり，都市 $ V_i $ 以外で降りることはできない．ある都市からある都市へ向けて運行されるバス路線が複数存在するかもしれない． JOI 国では間もなくオリンピックが開催される．JOI 国の運輸大臣である $ K $ 理事長は，バス路線を高々 $ 1 $ つ選び，オリンピック期間中，運賃を変更せずにそのバス路線の運行方向を反転させることにした．つまり，バス路線 $ i $ ($ 1\ \leqq\ i\ \leqq\ M $) を選んだ場合，オリンピック期間中，そのバス路線は都市 $ U_i $ から都市 $ V_i $ へ向けて運行されるのではなく，都市 $ V_i $ から都市 $ U_i $ へ向けて運行されるようになる．ただし，バス路線 $ i $ の運行方向の反転には $ D_i $ 円かかり，これは K 理事長のポケットマネーにより賄われる．また，混乱を避けるため，オリンピック期間の途中でバス路線を反転させることはできない． 運輸大臣である K 理事長は，オリンピック期間中，都市 $ 1 $ と都市 $ N $ の間をバス路線を乗り継いで往復する予定である．運行方向を反転させるバス路線をうまく選ぶことで，往復の合計運賃と運行方向の反転の費用との和を最小化したい． 都市の個数と，バス路線の情報が与えられたとき，運行方向を反転させるバス路線をうまく選ぶことで，都市 $ 1 $ と都市 $ N $ の間の往復の合計運賃と，運行方向の反転の費用との和の最小値を求めるプログラムを作成せよ．ただし，どのようにバス路線を選んでも都市 $ 1 $ と都市 $ N $ の間を往復することができない場合は，代わりに $ −1 $ を出力せよ． - - - - - -

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である． > $ N $ $ M $ $ U_1 $ $ V_1 $ $ C_1 $ $ D_1 $ $ \vdots $ $ U_M $ $ V_M $ $ C_M $ $ D_M $

都市 $ 1 $ と都市 $ N $ の間の往復の合計運賃と，運行方向の反転の費用との和の最小値を，標準出力に $ 1 $ 行で出力せよ．ただし，どのようにバス路線を選んでも都市 $ 1 $ と都市 $ N $ の間を往復することができない場合は，代わりに $ −1 $ を出力せよ． - - - - - -

### 制約 - $ 2\ \leqq\ N\ \leqq\ 200 $． - $ 1\ \leqq\ M\ \leqq\ 50\,000 $． - $ 1\ \leqq\ U_i\ \leqq\ N $ ($ 1\ \leqq\ i\ \leqq\ M $)． - $ 1\ \leqq\ V_i\ \leqq\ N $ ($ 1\ \leqq\ i\ \leqq\ M $)． - $ U_i\ \neq\ V_i $ ($ 1\ \leqq\ i\ \leqq\ M $)． - $ 0\ \leqq\ C_i\ \leqq\ 1\,000\,000 $ ($ 1\ \leqq\ i\ \leqq\ M $)． - $ 0\ \leqq\ D_i\ \leqq\ 1\,000\,000\,000 $ ($ 1\ \leqq\ i\ \leqq\ M $)． ### 小課題 1. ($ 5 $ 点) $ M\ \leqq\ 1\,000 $． 2. ($ 11 $ 点) $ M $ は偶数，$ U_{2i\ −\ 1}\ =\ U_{2i} $，$ V_{2i\ −\ 1}\ =\ V_{2i} $，$ C_{2i\ −\ 1}\ =\ C_{2i} $ ($ 1\ \leqq\ i\ \leqq\ \frac{M}{2} $)． 3. ($ 21 $ 点) $ C_i\ =\ 0 $ ($ 1\ \leqq\ i\ \leqq\ M $)． 4. ($ 63 $ 点) 追加の制約はない． - - - - - - ### Sample Explanation 1 バス路線 $ 2 $ の運行方向を費用 $ 1 $ で反転させると，都市 $ 1 $ から都市 $ 4 $ への移動にかかる運賃は最小で $ 6 $，都市 $ 4 $ から都市 $ 1 $ への移動にかかる運賃は最小で $ 3 $ となり，都市 $ 1 $ と都市 $ 4 $ の間の往復の合計運賃と，運行方向の反転の費用との和は $ 10 $ となる． 都市 $ 1 $ と都市 $ 4 $ の間の往復の合計運賃と，運行方向の反転の費用との和を $ 10 $ より小さくすることはできないので，$ 10 $ を出力する． - - - - - - ### Sample Explanation 2 この入出力例は小課題 $ 2 $ の制約を満たす． - - - - - - ### Sample Explanation 3 この入出力例は小課題 $ 3 $ の制約を満たす． - - - - - - ### Sample Explanation 4 バス路線の運行方向を反転させなくてもよい． - - - - - - ### Sample Explanation 5 この入力例では，都市 $ 4 $ から都市 $ 3 $ へと運行されるバス路線が $ 2 $ 本存在する．