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

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

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

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

制約

• 2 \leqq N \leqq 200．
• 1 \leqq M \leqq 50\,000．
• 1 \leqq U_i \leqq N (1 \leqq i \leqq M)．
• 1 \leqq V_i \leqq N (1 \leqq i \leqq M)．
• U_i \neq V_i (1 \leqq i \leqq M)．
• 0 \leqq C_i \leqq 1\,000\,000 (1 \leqq i \leqq M)．
• 0 \leqq D_i \leqq 1\,000\,000\,000 (1 \leqq i \leqq M)．

小課題

1. (5 点) M \leqq 1\,000．
2. (11 点) M は偶数，U_{2i − 1} = U_{2i}，V_{2i − 1} = V_{2i}，C_{2i − 1} = C_{2i} (1 \leqq i \leqq \frac{M}{2})．
3. (21 点) C_i = 0 (1 \leqq i \leqq M)．
4. (63 点) 追加の制約はない．

入力例 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 の運行方向を費用 1 で反転させると，都市 1 から都市 4 への移動にかかる運賃は最小で 6，都市 4 から都市 1 への移動にかかる運賃は最小で 3 となり，都市 1 と都市 4 の間の往復の合計運賃と，運行方向の反転の費用との和は 10 となる．

都市 1 と都市 4 の間の往復の合計運賃と，運行方向の反転の費用との和を 10 より小さくすることはできないので，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

この入出力例は小課題 2 の制約を満たす．

入力例 3

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

出力例 3

2

この入出力例は小課題 3 の制約を満たす．

入力例 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

この入力例では，都市 4 から都市 3 へと運行されるバス路線が 2 本存在する．