滑降競技

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

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

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

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

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

Input

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

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 行に、２つの旗を結ぶラインの情報が与えられる。各行には、ラインの始点である旗の番号 s_i (1 ≤ s_i < N)、終点である旗の番号 e_i (1 < e_i ≤ N)、１回目に通るときの所要時間 t_i,1 (1 ≤ t_i,1 ≤ 100000)、同じラインを２回目に通ったときの所要時間(1 ≤ t_i,2 ≤ 100000) が与えられる。

Output

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

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