あなたは磐梯山で開催されるスキー競技に参加します。この競技では、ゲレンデを各選手が２回滑降し、その合計時間の短さを競います。ゲレンデにはいくつもの旗が立っていて、それらの間には選手が通るラインが設定されています。選手はスタート地点からゴール地点まで、ラインをたどりながら滑降します。ラインは以下のように設定されています。
- ゴール地点以外の旗からは一本以上のラインが延びている。
- ある旗とある旗を直接結ぶラインは多くても一つしかない。
- ラインは決まった方向にしか滑降できない。
- どの旗にも必ずスタートからたどり着くことができ、どの旗からもゴールにたどり着ける。
- どのようにラインをたどっていっても、同じ旗に戻ることはない。
選手は現在いる旗から延びているラインを選んで次に行く旗を決めることができます。ラインの選び方は自由なので、選手は滑降ごとに異なるラインを通ってゴールに向かうことができます。
競技前夜、スポーツドクターのソルト君が、あなたが滑るときのゲレンデの状態を予想してくれました。それによると、１回目の滑降で通ったラインは通過の影響で雪質が変わってしまうため、２回目の滑降で同じラインを通ると 、かかる時間が変わることがあるそうです。ソルト君は、それぞれのラインを１回目に通るときの時間と、２回目に通るときの時間を教えてくれました。あなたはこの情報をたよりに、２回の滑降の合計時間を最短にする滑り方を朝までに見つけなければなりません。
課題
ゲレンデの状態が与えられたとき、２回の滑降の合計時間でもっとも短い値を計算するプログラムを作成せよ 。
入力
入力は以下の形式で与えられる
N P s1 e1 t1,1 t1,2 s2 e2 t2,1 t2,2 : sP eP tP,1 tP,2
１行目に、旗の数N(2≦N≦1000)と２つの旗を結ぶラインの数P(1≦P≦2000)が与えられる。旗には1からNまでの番号が振られていて、スタート地点の旗の番号が1、ゴール地点の旗の番号がNである。続くP行に、２つの旗を結ぶラインの情報が与えられる。各行には、ラインの始点である旗の番号si(1≦si＜N)、終点である旗の番号ei(1＜ei≦N)、１回目に通るときの所要時間ti,1(1≦ti,1≦100000)、同じラインを２回目に通ったときの所要時間(1≦ti,2≦100000)が与えられる。
時間制限
入力に対して、実行時間が５秒を超えてはならない。
出力
２回の滑降の合計時間でもっとも短い値を１行に出力する。
入出力例
入力例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