あなたは磐梯山で開催されるスキー競技に参加します。この競技では、ゲレンデを各選手が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回目に通ったときの所要時間ti,2 (1 ≤ ti,2 ≤ 100000) が与えられる。
2回の滑降の合計時間でもっとも短い値を1行に出力する。
3 3 1 2 1 2 2 3 1 2 1 3 1 3
3
3 3 1 2 1 2 2 3 1 2 1 3 1 1
2
4 5 1 2 3 5 1 3 1 3 3 2 2 5 2 4 6 1 3 4 5 5
13