問題文

N 個の空港があり、各空港は 1 から N の番号で表されます。

M 便のフライトがあり、i 番目のフライトは空港 a_i から 空港 b_i へ移動し、出発時刻は s_i 、到着時刻は t_i です。 空港から空港へはフライトでのみ移動できます。乗り換えにかかる時間は無視できる、つまり乗っていたフライトの到着と同時に出発する別のフライトに乗り換えることが可能であるとします。

空港 1 から空港 N へなるべく移動時間が短くなるように移動するときの移動時間を求めてください。ただし、たどり着く方法が存在しない場合は -1 を出力してください。ここで、移動時間は空港 1 を出発した時刻を S、空港 N に到着した時刻を T として、T - S で表されます。

制約

• 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
• 入力はすべて整数

小課題

1. ( 1 点) a_i = 1 ならば s_i = 0
2. ( 99 点) 追加の制約はない

入力例 1

3 3
1 3 0 5
1 2 3 4
2 3 6 7

出力例 1

4

時刻 3 に出発して、フライト 2 、フライト 3 に乗ることで時刻 7 に到着します。

このテストケースは小課題 1 の制約を満たしません。

入力例 2

2 0

出力例 2

-1

たどり着く方法が存在しない場合は -1 を出力してください。

このテストケースは小課題 1 の制約を満たします。

入力例 3

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

出力例 3

3

乗り換えにかかる時間は無視できます。

このテストケースは小課題 1 の制約を満たします。