该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

最近飞机经常出问题，导致 $TooY0ung$ 出行尽量会选择火车。

又到了日常赶火车的环节，除了马路以外 $TooY0ung$ 还可能要横穿商场和小区以保证自己能赶得上火车。

显然，小区和商场不是并全天开放的。

不过还好 $TooY0ung$ 已经事先调查好了每一条可能用得上的道路，调查内容包括 $n$ 个地点（从 $1$ 到 $n$ 编号）和 $m$ 条双向道路。

$TooY0ung$ 清楚地知道每条道路的起止地点、通过所需时间 $si$ 以及 道路的开放时刻 $ti$ 。

一条道路的开放时刻 $ti$ 是指从 $ti$ 时刻开始这道路才可以使用，在 $ti$ 时刻以前（不包括 $ti$ 时刻）该道路都是不可进入的状态。

$TooY0ung$ 需要从酒店（起点 $s$ ）到达火车站（终点 $e$ ），你需要做的是写一个程序来求出 $TooY0ung$ 最早能在什么时刻到达火车站。

（我们将起点 $s$ 指定为编号为 $1$ 的地点，终点 $e$ 指定为编号为 $n$ 的地点。）

输入格式

第 $1$ 行：两个由空格分开的正整数 $n$ 和 $m$， 表示有 $n$ 个地点以及 $m$ 条道路；

第 $2$ 至 $m+1$ 行：每行有四个由空格分开的正整数 $xi, yi, si, ti$， 表示第 $i$ 条双向道路将 $xi$ 与 $yi$ 两个地点连接在一起，通过它需要 $si$ 个单位时间，它只有在时刻 $ti$ 开始才可以使用。

输出格式

一行一个正整数 $z$， 表示最早到达的时刻。（数据保证 $z$ 一定存在）

3 3
1 2 4 100
2 3 2 100
1 3 5 99

104

样例解释

$3$ 个点，$3$ 条边，起点是 $1$，终点是 $3$。我们走第三条边，他在 $99$ 时刻可以通过，那么我们等到 $99$ 这个时间，花费 $5$ 的时间走过去，总时间是：$99 + 5 = 104$。

可以证明，这是最优的方案。

liang 心出题人的提示

作为 liang 心出题人，不会把具体的时间带进数据里，$TooY0ung$ 从 $0$ 时刻出发，最早 $z$ 时刻到达，每一条道路的开放时刻和通过所需时间都是整数。

你只需要求出这个 $z$ 并把它输出出来就可以轻松地拿下本题完成清明节比赛的第二题。

数据规模与约定

对于 $100\%$ 的数据，$1 \le n \le 10^5，1 \le m \le 2 * 10^5，1 \le xi,yi \le n ，0 \le si，ti \le 10^9$。