010 - 滑降競技

時間制限 1 秒 / メモリ制限 256 MB / 得点 16 / x 0 /


TLE
1sec
MLE
256MB
得点
16

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

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

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

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

課題

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

入力

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

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<ei≦N)、1回目に通るときの所要時間ti,1(1≦ti,1≦100000)、同じラインを2回目に通ったときの所要時間(1≦ti,2≦100000)が与えられる。

時間制限

入力に対して、実行時間が5秒を超えてはならない。

出力

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

入出力例

入力例1

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

出力例1

3

入力例2

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

出力例2

2

入力例3

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

出力例3

13