G - カメレオン Editorial /

Time Limit: 4 sec / Memory Limit: 256 MB

問題文

ここはとあるジャングル、あなたの友達のカメレオンが生活しているところです。

ジャングルには 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 行に出力せよ。出力の末尾にも改行を入れること。

入力例1

6 7
1 2 1 6
1 3 7 4
2 3 3 4
2 5 6 6
3 4 4 6
3 5 1 3
5 6 2 4

出力例1

22

この入力例の場合、以下のように移動するのが最適です。

  • 最初、広場 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 となります。

入力例2

3 3
1 2 1 10
1 3 3 3
2 3 5 2

出力例2

5