AT_abc204_e [ABC204E] Rush Hour 2

AtCoder 国有 $N$ 个城市和 $M$ 条道路。 城市编号为 $1$ 到 $N$，道路编号为 $1$ 到 $M$。第 $i$ 条道路连接城市 $A_i$ 和城市 $B_i$，且为双向道路。 AtCoder 国存在以时刻 $0$ 为高峰的“高峰时段”。如果在时刻 $t$ 开始通过第 $i$ 条道路，则需要花费 $C_i + \left\lfloor \frac{D_i}{t+1} \right\rfloor$ 的时间才能通过（$\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数）。 高桥君可以在时刻 $0$ 或之后的**整数时刻**从城市 $1$ 出发，通过道路前往城市 $N$。 高桥君可以在每个城市**等待整数时间**。请输出高桥君能够到达城市 $N$ 的最早时刻。如果无法到达城市 $N$，则输出 $-1$。 已知在题目限制下，答案一定为整数。

输入以以下格式从标准输入读入。 > $N$ $M$ > $A_1$ $B_1$ $C_1$ $D_1$ > $\vdots$ > $A_M$ $B_M$ $C_M$ $D_M$

输出高桥君能够到达城市 $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$ - 输入均为整数 ### 样例解释 1 首先在城市 $1$ 等待到时刻 $1$。然后在时刻 $1$ 通过第 $1$ 条道路移动，所需时间为 $2+\left\lfloor \frac{3}{1+1} \right\rfloor = 3$，因此在时刻 $4$ 到达城市 $2$。无法更早到达城市 $2$。 ### 样例解释 2 可能存在多条道路连接同一对城市，或存在连接同一城市的自环道路。 ### 样例解释 3 也可能不存在从城市 $1$ 到城市 $N$ 的路径。 由 ChatGPT 4.1 翻译