有 $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 分）如果 $a_i = 1$，则 $s_i = 0$。
2.（99 分）无其它额外限制。

样例解释 1

可以在时刻 $3$ 出发，乘坐航班 $2$ 和航班 $3$，在时刻 $7$ 到达。

本测试用例不满足子任务 $1$ 的条件。

样例解释 2

如果不存在到达的方法，请输出 $-1$。

本测试用例满足子任务 $1$ 的条件。

样例解释 3

换乘时间可以忽略。

本测试用例满足子任务 $1$ 的条件。

数据范围与约定

• $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$
• 所有输入均为整数。

由 ChatGPT 5 翻译