AT_code_thanks_festival_2015_g カメレオン

[problemUrl]: https://atcoder.jp/contests/code-thanks-festival-2015-open/tasks/code_thanks_festival_2015_g ここはとあるジャングル、あなたの友達のカメレオンが生活しているところです。 ジャングルには $ N $ 個の広場があり、広場には $ 1 $ から $ N $ までの番号が付けられています。また、ジャングルには $ M $ 本の道があり、道には $ 1 $ から $ M $ までの番号が付けられています。どの道も異なる $ 2 $ つの広場を結んでいて、双方向に移動可能です。 あなたの友達のカメレオンは、CODE THANKS FESTIVAL 2015 に参加するため、広場 $ 1 $ から広場 $ N $ に向かおうとしています。カメレオンは広場間を移動する際に道を使いますが、ジャングルの道は未知なる危険に満ちあふれているため、道 $ i\ (1\ ≦\ i\ ≦\ M) $ を使用する際にはカメレオンの体色は色 $ c_i $ でなければなりません。また、道 $ i $ を使用して移動する際、時間が $ t_i $ だけかかります。 カメレオンは広場 $ 1 $ から移動を開始する際、体色は色 $ 1 $ です。カメレオンはどの広場でも体色を変化させることができますが、どの広場でも色 $ x $ から色 $ y $ に体色を変化させるには時間が ｜$ x-y $｜ だけかかってしまいます。またカメレオンは広場 $ N $ に到着したならば移動を終了しますが、この際の体色はどの色でも構いません。 あなたは、カメレオンが広場 $ N $ に到着するまでにかかるの時間として考えられる最小値を求めることになりました。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ a_1 $ $ b_1 $ $ c_1 $ $ t_1 $ $ a_2 $ $ b_2 $ $ c_2 $ $ t_2 $ : $ a_M $ $ b_M $ $ c_M $ $ t_M $ - $ 1 $ 行目には、広場の個数 $ N\ (2\ ≦\ N\ ≦\ 40,000) $ および道の本数 $ M\ (1\ ≦\ M\ ≦\ 80,000) $ が空白区切りで与えられる。 - $ 2 $ 行目から $ M $ 行には、道に関する情報が与えられる。このうち $ i\ (1\ ≦\ i\ ≦\ M) $ 行目では $ 4 $ つの整数値 $ a_i $, $ b_i\ (1\ ≦\ a_i\ ＜\ b_i\ ≦\ N) $, $ c_i\ (1\ ≦\ c_i\ ≦\ 1,000,000,000) $, $ t_i\ (1\ ≦\ t_i\ ≦\ 1,000,000,000) $ が空白区切りで与えられる。これは、道 $ i $ が広場 $ a_i $ と $ b_i $ を結んでおり、道 $ i $ を渡る際には体色が色 $ c_i $ でなければならず、移動に時間が $ t_i $ かかることを表す。 - $ i $ ≠ $ j $ ならば、$ a_i $ ≠ $ a_j $ あるいは $ b_i $ ≠ $ b_j $ が成立する。 - 広場 $ 1 $ から他のどの広場にも $ 1 $ 本以上の道を経由して行き来できることは保証されている。

カメレオンが広場 $ N $ に到着するまでにかかる時間として考えられる最小値を $ 1 $ 行に出力せよ。出力の末尾にも改行を入れること。

### Sample Explanation 1 この入力例の場合、以下のように移動するのが最適です。 - 最初、広場 $ 1 $ に体色が色 $ 1 $ のカメレオンがいます。 - 道 $ 1 $ を用いて広場 $ 1 $ から広場 $ 2 $ に移動します。カメレオンの体色が色 $ 1 $ なので移動可能であり、合計でかかった時間は $ 6 $ となります。 - 広場 $ 2 $ で体色を色 $ 1 $ から色 $ 3 $ に変化させます。合計でかかった時間は $ 6+2 $ = $ 8 $ となります。 - 道 $ 3 $ を用いて広場 $ 2 $ から広場 $ 3 $ に移動します。カメレオンの体色が色 $ 3 $ なので移動可能であり、合計でかかった時間は $ 8+4 $ = $ 12 $ となります。 - 広場 $ 3 $ で体色を色 $ 3 $ から色 $ 1 $ に変化させます。合計でかかった時間は $ 12+2 $ = $ 14 $ となります。 - 道 $ 6 $ を用いて広場 $ 3 $ から広場 $ 5 $ に移動します。カメレオンの体色が色 $ 1 $ なので移動可能であり、合計でかかった時間は $ 14+3 $ = $ 17 $ となります。 - 広場 $ 6 $ で体色を色 $ 1 $ から色 $ 2 $ に変化させます。合計でかかった時間は $ 17+1 $ = $ 18 $ となります。 - 道 $ 7 $ を用いて広場 $ 5 $ から広場 $ 6 $ に移動します。カメレオンの体色が色 $ 2 $ なので移動可能であり、合計でかかった時間は $ 18+4 $ = $ 22 $ となります。