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 分）如果 $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 翻译