CF827F.Dirty Arkady's Kitchen

Arkady likes to walk around his kitchen. His labyrinthine kitchen consists of several important places connected with passages. Unfortunately it happens that these passages are flooded with milk so that it's impossible to pass through them. Namely, it's possible to pass through each passage in any direction only during some time interval.

The lengths of all passages are equal and Arkady makes through them in one second. For security reasons, Arkady can never stop, also, he can't change direction while going through a passage. In other words, if he starts walking in some passage, he should reach its end and immediately leave the end.

Today Arkady needs to quickly reach important place n from place 1. He plans to exit the place 1 at time moment 0 and reach the place n as early as he can. Please find the minimum time he should spend on his way.

阿尔卡季喜欢在厨房里散步。他那迷宫般的厨房由若干个重要地点通过通道连接而成。不幸的是，这些通道有时会被牛奶淹没，导致无法通行。具体来说，每条通道仅在某个时间区间内可以双向通行。

所有通道的长度相等，阿尔卡季穿过任意一条通道均需恰好 1 秒。出于安全原因，阿尔卡季在行走过程中绝不能停下，且在穿过某条通道时也不能改变方向。换言之，一旦他开始沿某条通道行走，就必须走到其终点，并立即离开该终点。

今天，阿尔卡季需要尽快从地点 1 到达地点 $n$。他计划在时刻 0 离开地点 1，并尽可能早地抵达地点 $n$。请计算他完成这段行程所需的最短时间。

The first line contains two integers n and m (1 ≤ n ≤ 5·105, 0 ≤ m ≤ 5·105) — the number of important places and the number of passages, respectively.

After that, m lines follow, each of them describe one passage. Each line contains four integers a, b, l and r (1 ≤ a, b ≤ n, a ≠ b, 0 ≤ l < r ≤ 109) — the places the passage connects and the time segment during which it's possible to use this passage.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 5\cdot10^5$，$0 \leq m \leq 5\cdot10^5$），分别表示重要地点的数量和通道的数量。

随后是 $m$ 行，每行描述一条通道。每行包含四个整数 $a$、$b$、$l$ 和 $r$（$1 \leq a, b \leq n$，$a \neq b$，$0 \leq l < r \leq 10^9$），表示该通道所连接的两个地点，以及可以使用该通道的时间区间。

Print one integer — minimum time Arkady should spend to reach the destination. If he can't reach the place n, print -1.

输出一个整数——Arkady 到达目的地所需的最短时间。如果他无法到达位置 $n$，则输出 $-1$。

In the first example Arkady should go through important places 1 → 3 → 4 → 5.

In the second example Arkady can't start his walk because at time moment 0 it's impossible to use the only passage.

在第一个例子中，阿尔卡季应依次经过重要地点 $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$。

在第二个例子中，阿尔卡季无法开始他的行走，因为在时刻 $0$，唯一的一条通道无法使用。