不稳定的道路

题目限制

2000 ms 256 M

题目描述

有 $n$ 个城市和 $m$ 条道路。城市编号 $1$ 至 $n$ ，道路编号 $1$ 到 $m$ 。道路 $i$ 双向连接城市 $a[i]$ 和城市 $b[i]$ 。

但是通过每一条道路，所需的时间却是不稳定的，跟出发的时刻有关，如果在时刻 $t$ 通过道路 $i$ ，那么需要的时间为：$c[i]+ \lfloor \frac{d[i]}{t+1} \rfloor$。其中 $c[i]$ 和 $d[i]$ 是给出的整数，并且上面这个式子的计算需要向下取整。

你计划从城市 $1$ 去往城市 $n$ ，这个过程中你可以在任何城市进行停留（不必立即出发）。问最早到达城市 $n$ 的时间。如果无法到达城市 $n$ ，请输出 $-1$ 。

输入格式

第一行输入两个数n,m，分别表示城市和道路的数量。（n,m≤1e5） 之后m行，每行4个数a[i],b[i],c[i],d[i]，描述一条道路。

输出格式

输出对应的答案，如果不能到达城市n，输出-1。

数据范围

对于 $20\%$ 的数据 $2 \le n \le 10, 0 \le m \le 10$

对于 $45\%$ 的数据 $2 \le n \le 300, 0 \le m \le 10^5$

对于 $100\%$ 的数据 $2 \le n \le 10^5, 0 \le m \le 10^5, 1 \le a[i],b[i] \le n,0 \le c[i],d[i] \le 10^9$

输入样例

2 1
1 2 2 3

输出样例

4