Downhill Race

Time Limit : 1 sec, Memory Limit : 262144 KB

滑降競技

あなたは磐梯山で開催されるスキー競技に参加します。この競技では、ゲレンデを各選手が2回滑降し、その合計時間の短さを競います。ゲレンデにはいくつもの旗が立っていて、それらの間には選手が通るラインが設定されています。選手はスタート地点からゴール地点まで、ラインをたどりながら滑降します。ラインは以下のように設定されています。

  • ゴール地点以外の旗からは一本以上のラインが延びている。
  • ある旗とある旗を直接結ぶラインは多くても一つしかない。
  • ラインは決まった方向にしか滑降できない。
  • どの旗にも必ずスタートからたどり着くことができ、どの旗からもゴールにたどり着ける。
  • どのようにラインをたどっていっても、同じ旗に戻ることはない。

選手は現在いる旗から延びているラインを選んで次に行く旗を決めることができます。ラインの選び方は自由なので、選手は滑降ごとに異なるラインを通ってゴールに向かうことができます。

競技前夜、スポーツドクターのソルト君が、あなたが滑るときのゲレンデの状態を予想してくれました。それによると、1回目の滑降で通ったラインは通過の影響で雪質が変わってしまうため、2回目の滑降で同じラインを通ると、かかる時間が変わることがあるそうです。ソルト君は、それぞれのラインを1回目に通るときの時間と、2回目に通るときの時間を教えてくれました。あなたはこの情報をたよりに、2回の滑降の合計時間を最短にする滑り方を朝までに見つけなければなりません。

ゲレンデの状態が与えられたとき、2回の滑降の合計時間でもっとも短い値を計算するプログラムを作成せよ。

Input

入力は以下の形式で与えられる。

N P
s1 e1 t1,1 t1,2
s2 e2 t2,1 t2,2
:
sP eP tP,1 tP,2

1行目に、旗の数 N (2 ≤ N ≤ 1000) と2つの旗を結ぶラインの数 P (1 ≤ P ≤ 2000) が与えられる。旗には 1 から N までの番号が振られていて、スタート地点の旗の番号が1、ゴール地点の旗の番号が N である。続く P 行に、2つの旗を結ぶラインの情報が与えられる。各行には、ラインの始点である旗の番号 si (1 ≤ si < N)、終点である旗の番号 ei (1 < eiN)、1回目に通るときの所要時間 ti,1 (1 ≤ ti,1 ≤ 100000)、同じラインを2回目に通ったときの所要時間(1 ≤ ti,2 ≤ 100000) が与えられる。

Output

2回の滑降の合計時間でもっとも短い値を1行に出力する。

Sample Input 1

3 3
1 2 1 2
2 3 1 2
1 3 1 3

Sample Output 1

3

Sample Input 2

3 3
1 2 1 2
2 3 1 2
1 3 1 1

Sample Output 2

2

Sample Input 3

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

Sample Output 3

13

Source: PC Koshien 2015 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2015-9-12
http://web-ext.u-aizu.ac.jp/pc-concours/