E - 匆忙时刻2

得分：500分

问题描述

AtCoder共有$N$个城市和$M$条道路。

城市编号为$1$到$N$，道路编号为$1$到$M$。第$i$条道路在城市$A_i$和城市$B_i$之间双向连接。

该国存在一个高峰期，峰值出现在时间0。如果你从时间$t$开始通过第$i$条道路，到达另一端需要$C_i+ \left\lfloor \frac{D_i}{t+1} \right\rfloor$时间单位。（$\lfloor x\rfloor$表示不超过$x$的最大整数。)

高桥计划在时间0或稍后的整数时刻从城市1出发，前往城市N。

如果高桥可以在每个城市停留整数时间单位的情况下，打印高桥可以到达城市N的最早时间。根据这个问题的约束条件，可以证明答案是一个整数。

如果城市N无法到达，请打印-1。

约束条件

• $2 \leq N \leq 10^5$
• $0 \leq M \leq 10^5$
• $1 \leq A_i,B_i \leq N$
• $0 \leq C_i,D_i \leq 10^9$
• 输入中的所有值都是整数。

输入

从标准输入中按以下格式获取输入：

$N$ $M$

$A_1$ $B_1$ $C_1$ $D_1$

$\vdots$

$A_M$ $B_M$ $C_M$ $D_M$

输出

输出一个整数，表示高桥可以到达城市N的最早时间，如果城市N无法到达，则输出-1。

2 1
1 2 2 3

4

我们首先在城市1停留，直到时间1。然后，在时间1开始，我们开始走第1条道路，到达城市2需要$2+\left\lfloor \frac{3}{1+1} \right\rfloor = 3$个时间单位，在时间4到达城市2。

不可能在时间4之前到达城市2。

2 3
1 2 2 3
1 2 2 1
1 1 1 1

3

可能有多条连接相同城市对的道路，也可能有通往同一城市的道路。

4 2
1 2 3 4
3 4 5 6

-1

可能不存在从城市1到城市N的路径。

6 9
1 1 0 0
1 3 1 2
1 5 2 3
5 2 16 5
2 6 1 10
3 4 3 4
3 5 3 10
5 6 1 100
4 2 0 110

20