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 $ n, m \in \mathbb{Z} $ denote the number of nodes and edges, respectively.
Let $ G = (V, E) $ be a directed graph where $ V = \{1, 2, \dots, n\} $, and for each undirected passage $ (a, b, l, r) $, add two directed edges:
- $ (a, b) $ with time window $ [l, r] $,
- $ (b, a) $ with time window $ [l, r] $.
Each edge has unit traversal cost (1 second).
**Constraints**
1. $ 1 \leq n \leq 5 \cdot 10^5 $
2. $ 0 \leq m \leq 5 \cdot 10^5 $
3. For each edge $ (u, v, l, r) $: $ 1 \leq u, v \leq n $, $ u \ne v $, $ 0 \leq l < r \leq 10^9 $
4. Arkady starts at node $ 1 $ at time $ 0 $.
5. Arkady must traverse edges continuously without stopping or changing direction mid-edge.
**Objective**
Find the minimum arrival time at node $ n $, starting from node $ 1 $ at time $ 0 $, such that for each traversed edge $ (u, v) $ with window $ [l, r] $, the arrival time at $ u $, say $ t $, satisfies $ t \in [l, r] $, and the arrival time at $ v $ is $ t + 1 $.
If no such path exists, output $ -1 $.