Time limit: 1 seconds

Memory limit: 512 megabytes

The thing that's between us is fascination, and the fascination resides in our being alike. Whether you're a man or a woman, the fascination resides in finding out that we're alike. —Practicalities, Writer, Marguerite Duras

题目描述

​ 初入PKU晓神拿起了一本中国现代史饶有兴趣地阅读着, 她发现中国作为基建狂魔, 在交通建设方面飞速发展. 这时他又想Frank能从Fuzhou去Beijing找她玩. 于是她想到了如下问题:

​ 中国大陆可以看作一个$N$个点$M$条路的无向图, 在这$M$条路中，第$i$条路$(A_i,B_i)$都有一个初始长度$C_i+D_i$, 由于中国交通飞速发展, 在第$j^{th}$个时刻通过$i^{th}$条道路的时间为$C_i+\lfloor\frac{D_i}{j}\rfloor$我们认为如果Frank在$j^{th}$时刻选择通过$i^{th}$条路, 他可以在第$j^{th}$时刻从$A_i$消耗$C_i+\lfloor\frac{D_i}{j}\rfloor$个单位时间到达$B_i$. 在每个时刻, Frank可以选择一条路走, 或者停留在原地.

​ 晓神希望Frank尽早去PKU找他玩, 于是她想请问聪明的你, Frank至少需要多少单位时间从Fuzhou(1号点)前往Beijing(N号点).

​ 特别地: 我们认为Frank是从第1时刻开始行动的.

输入

第一行包含两个整数$N,M$.

接下来$M$行每行四个整数$A_i,B_i,C_i,D_i$表示一条连接$(A_i,B_i)$的无向边.

输出

输出一个整数表示Frank到达Beijing的最少时间.

限制

• $1\leq N\leq10^5$.
• $1\leq M\leq2\times10^5$.
• $1\leq A_i,B_i\leq N$.
• $1\leq C_i,D_i\leq10^9$.
• 图保证联通且没有重边和自环.

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

Tips

For someone special: May your future travels, and the love of every hike, every look at the sea, every embrace in the landscape, can become each other's life, a flowing feast. Never go on trips with anyone you do not love.