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.
## Input
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.
## Output
Print one integer — minimum time Arkady should spend to reach the destination. If he can't reach the place _n_, print _\-1_.
[samples]
## Note
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.
Arkady 喜欢在厨房里散步。他的迷宫式厨房由若干重要区域通过通道连接而成。不幸的是，这些通道被牛奶淹没，导致无法通行。具体来说，每个通道仅在某个时间区间内允许双向通行。
所有通道的长度相等，Arkady 穿过每个通道需要一秒钟。出于安全考虑，Arkady 不能停止，也不能在通过通道时改变方向。换句话说，如果他开始通过某条通道，就必须到达其另一端并立即离开该端点。
今天，Arkady 需要尽快从区域 #cf_span[1] 到达区域 #cf_span[n]。他计划在时间点 #cf_span[0] 离开区域 #cf_span[1]，并尽可能早地到达区域 #cf_span[n]。请计算他所需的最少时间。
第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 5·105]，#cf_span[0 ≤ m ≤ 5·105]）——分别表示重要区域的数量和通道的数量。
接下来 #cf_span[m] 行，每行描述一条通道。每行包含四个整数 #cf_span[a]、#cf_span[b]、#cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ a, b ≤ n]，#cf_span[a ≠ b]，#cf_span[0 ≤ l < r ≤ 109]）——表示该通道连接的两个区域，以及可以使用该通道的时间区间。
输出一个整数——Arkady 到达目的地所需的最少时间。如果他无法到达区域 #cf_span[n]，请输出 _-1_。
在第一个例子中，Arkady 应该经过重要区域 #cf_span[1 → 3 → 4 → 5]。
在第二个例子中，Arkady 无法开始行走，因为在时间点 #cf_span[0] 无法使用唯一的通道。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 5·105]，#cf_span[0 ≤ m ≤ 5·105]）——分别表示重要区域的数量和通道的数量。接下来 #cf_span[m] 行，每行描述一条通道。每行包含四个整数 #cf_span[a]、#cf_span[b]、#cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ a, b ≤ n]，#cf_span[a ≠ b]，#cf_span[0 ≤ l < r ≤ 109]）——表示该通道连接的两个区域，以及可以使用该通道的时间区间。
## Output
输出一个整数——Arkady 到达目的地所需的最少时间。如果他无法到达区域 #cf_span[n]，请输出 _-1_。
[samples]
## Note
在第一个例子中，Arkady 应该经过重要区域 #cf_span[1 → 3 → 4 → 5]。
在第二个例子中，Arkady 无法开始行走，因为在时间点 #cf_span[0] 无法使用唯一的通道。
**Definitions**
Let $ G = (V, E) $ be a directed graph where $ V = \{1, 2, \dots, n\} $ represents important places, and $ E $ consists of undirected edges with time windows: for each passage $ e \in E $, $ e = (a, b, l, r) $ with $ a, b \in V $, $ a \ne b $, and $ 0 \le l < r \le 10^9 $, meaning the passage between $ a $ and $ b $ is traversable only during the time interval $ [l, r) $, and traversal takes exactly 1 second.
**Constraints**
1. $ 1 \le n \le 5 \cdot 10^5 $
2. $ 0 \le m \le 5 \cdot 10^5 $
3. For each passage $ (a, b, l, r) $:
- $ 1 \le a, b \le n $, $ a \ne b $
- $ 0 \le l < r \le 10^9 $
4. Arkady starts at node $ 1 $ at time $ 0 $.
5. Arkady cannot stop or change direction mid-passage.
6. Upon arriving at a node at time $ t $, he may immediately depart via any available passage $ (u, v, l, r) $ only if $ t \in [l, r) $.
**Objective**
Find the minimum arrival time at node $ n $, starting from node $ 1 $ at time $ 0 $, using valid passages. If unreachable, return $ -1 $.
Formally, compute:
$$
\min \left\{ t \in \mathbb{R}_{\ge 0} \,\middle|\, \exists \text{ a path } 1 = v_0 \to v_1 \to \dots \to v_k = n \text{ with arrival times } t_0=0, t_1, \dots, t_k=t \text{ s.t. } \forall i, \, t_i \in [l_{i}, r_{i}) \right\}
$$
where each edge $ (v_i, v_{i+1}) $ has time window $ [l_i, r_i) $, and $ t_{i+1} = t_i + 1 $.