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

高峰时段

题目描述

某地区共有 $N$ 座城市和 $M$ 条双向道路，城市编号为 $1$ 到 $N$。

第 $i$ 条道路连接城市 $A_i$ 和城市 $B_i$。受高峰时段交通状况影响，道路的通行时间会随着出发时刻发生变化。

若在整数时刻 $t$ 开始通过第 $i$ 条道路，则通过该道路所需的时间为

其中，$\lfloor x\rfloor$ 表示不超过 $x$ 的最大整数。

一名调查员在时刻 $0$ 位于城市 $1$，需要前往城市 $N$。他可以在任意城市等待任意非负整数个时间单位，并在任意整数时刻选择一条相邻道路通行。

到达一座城市后，调查员可以在同一时刻立即开始通过下一条道路。因此，当道路的通行时间为 $0$ 时，他可以在同一时刻连续通过多条道路。

请计算调查员最早能够到达城市 $N$ 的时刻。

若无法从城市 $1$ 到达城市 $N$，输出 $-1$。

输入格式

第一行包含两个整数 $N$ 和 $M$（$2\leq N\leq 10^5$，$0\leq M\leq 10^5$），分别表示城市数量和道路数量。

接下来 $M$ 行，第 $i$ 行包含四个整数 $A_i$、$B_i$、$C_i$ 和 $D_i$（$1\leq A_i,B_i\leq N$，$0\leq C_i,D_i\leq 10^9$），表示第 $i$ 条道路连接城市 $A_i$ 和城市 $B_i$。

道路均为双向道路。输入中可能存在连接同一对城市的多条道路，也可能存在连接同一座城市的自环道路。

所有输入数据均为整数。

输出格式

输出一个整数，表示调查员最早到达城市 $N$ 的时刻。

若无法到达城市 $N$，输出 $-1$。

输入输出样例 #1

输入 #1

2 1
1 2 2 3

输出 #1

4

输入输出样例 #2

输入 #2

4 2
1 2 3 4
3 4 5 6

输出 #2

-1

说明/提示

在样例 1 中，调查员先在城市 $1$ 等待至时刻 $1$，然后开始通过道路。通过该道路所需的时间为

因此，调查员在时刻 $4$ 到达城市 $2$。不存在更早到达城市 $2$ 的方案。