给定一张 n 个点，m 条边的无向图，每条边有两个属性 c_i,d_i。
你现在位于点 1，想要前往点 n，现在的时间是 0。当时间为 t 时经过第 i 条边所需的时间是 c_i+\lfloor\frac{d_i}{t+1}\rfloor。
你可以在城市中停留任意非负整数时间，请求出你到达点 n 所花费的最短时间，如果无法到达，输出 `-1`。
第一行两个数字，n和m，分别表示n个点和m条边
接下来m行，每行四个数字，u,v,c,d分别表示u到v有一条边，c,d是该边的属性
到达点 n 所花费的最短时间，如果无法到达，输出 `-1`。
2 1 1 2 2 3
4
2 3 1 2 2 3 1 2 2 1 1 1 1 1
3
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
- 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 秒 |
| 内存限制 | 128 MB |