阿尔卡季的脏厨房

• 时间限制：5 秒
• 内存限制：512 MiB

题目描述

阿尔卡季的厨房像迷宫一样，由 (n) 个重要地点和若干连接它们的通道组成。每条通道都被牛奶淹没，只有在给定的时间区间内才能双向通行。

所有通道长度相同，穿过一条通道恰好需要 (1) 秒。出于安全原因，阿尔卡季不能停在某个地点等待；一旦进入通道，也不能中途掉头。也就是说，他到达一个地点后必须立即进入下一条当时可用的通道。

时刻 (0)，阿尔卡季位于地点 (1)。请计算他最早何时能到达地点 (n)。

输入格式

第一行两个整数 (n,m)，分别表示地点数和通道数。

接下来 (m) 行，每行四个整数 (a,b,l,r)，表示一条连接地点 (a,b) 的无向通道。阿尔卡季可以在整数时刻 (t) 进入这条通道，当且仅当 (l\le t<r)。

输出格式

输出到达地点 (n) 的最早时刻。若永远无法到达，输出 (-1)。

样例输入 1

5 6
1 2 0 1
2 5 2 3
2 5 0 1
1 3 0 1
3 4 1 2
4 5 2 3

样例输出 1

3

样例输入 2

2 1
1 2 1 100

样例输出 2

-1

样例说明

在第一组样例中，可以依次经过地点 (1\to3\to4\to5)。

在第二组样例中，时刻 (0) 不能进入唯一的通道，因此无法出发。

数据范围

对于全部数据，(1\le n\le5\cdot10^5)，(0\le m\le5\cdot10^5)，(1\le a,b\le n)，(a\ne b)，(0\le l<r\le10^9)。

题目来源：Codeforces 827F。