문제

JOI 国には $N$ 個の都市があり，$1$ から $N$ までの番号が付いている．また，都市と都市を一方向に結ぶ $M$ 本のバス路線があり，$1$ から $M$ までの番号が付いている．バス路線 $i$ ($1 \le i \le M$) は都市 $U_i$ から都市 $V_i$ へ向けて運行されており，運賃は $C_i$ 円である．バス路線 $i$ ($1 \le i \le M$) では，都市 $U_i$ 以外で乗ったり，都市 $V_i$ 以外で降りることはできない．ある都市からある都市へ向けて運行されるバス路線が複数存在するかもしれない．

JOI 国では間もなくオリンピックが開催される．JOI 国の運輸大臣である K 理事長は，バス路線を高々 $1$ つ選び，オリンピック期間中，運賃を変更せずにそのバス路線の運行方向を反転させることにした．つまり，バス路線 $i$ ($1 \le i \le M$) を選んだ場合，オリンピック期間中，そのバス路線は都市 $U_i$ から都市 $V_i$ へ向けて運行されるのではなく，都市 $V_i$ から都市 $U_i$ へ向けて運行されるようになる．ただし，バス路線 $i$ の運行方向の反転には $D_i$ 円かかり，これは K 理事長のポケットマネーにより賄われる．また，混乱を避けるため，オリンピック期間の途中でバス路線を反転させることはできない．

運輸大臣である K 理事長は，オリンピック期間中，都市 $1$ と都市 $N$ の間をバス路線を乗り継いで往復する予定である．運行方向を反転させるバス路線をうまく選ぶことで，往復の合計運賃と運行方向の反転の費用との和を最小化したい．

都市の個数と，バス路線の情報が与えられたとき，運行方向を反転させるバス路線をうまく選ぶことで，都市 $1$ と都市 $N$ の間の往復の合計運賃と，運行方向の反転の費用との和の最小値を求めるプログラムを作成せよ．ただし，どのようにバス路線を選んでも都市 $1$ と都市 $N$ の間を往復することができない場合は，代わりに $-1$ を出力せよ．

입력

入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である．

N M
U_1 V_1 C_1 D_1
...
U_M V_M C_M D_M

출력

都市 $1$ と都市 $N$ の間の往復の合計運賃と，運行方向の反転の費用との和の最小値を，標準出力に $1$ 行で出力せよ．ただし，どのようにバス路線を選んでも都市 $1$ と都市 $N$ の間を往復することができない場合は，代わりに $-1$ を出力せよ．

예제 입력 1

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

예제 출력 1

10

예제 입력 2

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

예제 출력 2

10

예제 입력 3

4 4
1 2 0 4
1 3 0 1
4 3 0 2
4 1 0 1

예제 출력 3

2

예제 입력 4

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

예제 출력 4

12

예제 입력 5

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

예제 출력 5

-1

제한

• $2 \le N \le 200$．
• $1 \le M \le 50\,000$．
• $1 \le U_i \le N$ ($1 \le i \le M$)．
• $1 \le V_i \le N$ ($1 \le i \le M$)．
• $U_i \ne V_i$ ($1 \le i \le M$)．
• $0 \le C_i \le 1\,000\,000$ ($1 \le i \le M$)．
• $0 \le D_i \le 1\,000\,000\,000$ ($1 \le i \le M$)．

서브태스크

1. ($5$ 점) $M \le 1000$．
2. ($11$ 점) $M$ は偶数，$U_{2i-1} = U_{2i}$，$V_{2i-1} = V_{2i}$，$C_{2i-1} = C_{2i}$ ($1 \le i \le \frac{M}{2}$)．
3. ($21$ 점) $C_i = 0$ ($1 \le i \le M$)．
4. ($63$ 점) 追加の制約はない．