#131. 旅行! 我就是想去旅行!

    ID: 131 Type: Default 1000ms 512MiB Tried: 8 Accepted: 1 Difficulty: 10 Uploaded By: Tags>福建师范大学第26届低年级程序设计竞赛

旅行! 我就是想去旅行!

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找她玩. 于是她想到了如下问题:

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

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

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

输入

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

接下来MM行每行四个整数Ai,Bi,Ci,DiA_i,B_i,C_i,D_i表示一条连接(Ai,Bi)(A_i,B_i)的无向边.

输出

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

限制

  • 1N1051\leq N\leq10^5.
  • 1M2×1051\leq M\leq2\times10^5.
  • 1Ai,BiN1\leq A_i,B_i\leq N.
  • 1Ci,Di1091\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.