AT_oupc2023_day1_k Minimize Transfer Time

$ N $ 個の空港があり、各空港は $ 1 $ から $ N $ の番号で表されます。 $ M $ 便のフライトがあり、 $ i $ 番目のフライトは空港 $ a_i $ から 空港 $ b_i $ へ移動し、出発時刻は $ s_i $ 、到着時刻は $ t_i $ です。 空港から空港へはフライトでのみ移動できます。乗り換えにかかる時間は無視できる、つまり乗っていたフライトの到着と同時に出発する別のフライトに乗り換えることが可能であるとします。 空港 $ 1 $ から空港 $ N $ へなるべく移動時間が短くなるように移動するときの移動時間を求めてください。ただし、たどり着く方法が存在しない場合は `-1` を出力してください。ここで、移動時間は空港 $ 1 $ を出発した時刻を $ S $ 、空港 $ N $ に到着した時刻を $ T $ として、 $ T - S $ で表されます。

入力は以下の形式で標準入力から与えられます。 > $ N $ $ M $ $ a_1 $ $ b_1 $ $ s_1 $ $ t_1 $ $ a_2 $ $ b_2 $ $ s_2 $ $ t_2 $ $ \vdots $ $ a_M $ $ b_M $ $ s_M $ $ t_M $

空港 $ 1 $ から空港 $ N $ へなるべく移動時間が短くなるように移動するときの移動時間を $ 1 $ 行で出力してください。ただし、たどり着く方法が存在しない場合は `-1` を出力してください。

### 小課題 1. ( $ 1 $ 点) $ a_i = 1 $ ならば $ s_i = 0 $ 2. ( $ 99 $ 点) 追加の制約はない ### Sample Explanation 1 時刻 $ 3 $ に出発して、フライト $ 2 $ 、フライト $ 3 $ に乗ることで時刻 $ 7 $ に到着します。 このテストケースは小課題 1 の制約を満たしません。 ### Sample Explanation 2 たどり着く方法が存在しない場合は `-1` を出力してください。 このテストケースは小課題 1 の制約を満たします。 ### Sample Explanation 3 乗り換えにかかる時間は無視できます。 このテストケースは小課題 1 の制約を満たします。 ### Constraints - $ 2 \leq N \leq 200{,}000 $ - $ 0 \leq M \leq 200{,}000 $ - $ 1 \leq a_i, b_i \leq N $ - $ 0 \leq s_i < t_i \leq 10^{9} $ - $ a_i \ne b_i $ - 入力はすべて整数