{"trustable":false,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"Problem Statement","value":{"format":"MD","content":"RioTian其实是一个星际国家的一个小领主,在他的领地里有N座星球和M条宇宙航线。\n假设星球的编号是1至N,航线的编号则为1至M。第i条航线双向连接星球 Ai 和星球 Bi\n在这个领地中,初始时间为0,如果你在时间点 t 通过航线 i,所需时间为 Ci + ⌊Di/(t + 1)⌋\n你现在想从星球1 到达星球N。你可以在每个星球可以停留**任意自然数**的时间。\n求你最早到达星球 N 的时间。如果无法到达星球N,输出 -1。\n"}},{"title":"Constraints","value":{"format":"MD","content":"2 \u003c\u003d N \u003c\u003d 10^5\n2\u003c\u003d M \u003c\u003d 10^5\n1 \u003c\u003d Ai,Bi \u003c\u003d N\n0 \u003c\u003d Ci,Di \u003c\u003d 10^9\n输入中的所有值都是整数"}},{"title":"Input","value":{"format":"MD","content":"输入从标准输入以以下格式给出:\nN M\nA1 B1 C1 D1\n⋮\nAM BM CM DM"}},{"title":"Output","value":{"format":"MD","content":"打印一个整数,表示你可以到达星球 N 的最早时间,如果星球 N 不可达,则输出 -1。"}},{"title":"Sample Input 1","value":{"format":"MD","content":"\u003ch3\u003e\u003c/h3\u003e\n\u003cpre\u003e2 1\n1 2 2 3\n\u003c/pre\u003e"}},{"title":"Sample Output 1","value":{"format":"MD","content":"\u003ch3\u003e\u003c/h3\u003e\n\u003cpre\u003e4\n\u003c/pre\u003e \n我们将首先留在星球 1 直到时间 1。 然后,在时间 1 ,我们将开始通过航线 1 ,在时间 4 到达星球 2 之前需要 2 + ⌊ 3/(1 + 1) ⌋ \u003d 3 个时间单位。\n 不可能在时间 4 之前到达星球 2。"}},{"title":"Sample Input 2","value":{"format":"MD","content":"\u003ch3\u003e\u003c/h3\u003e\n\u003cpre\u003e2 3\n1 2 2 3\n1 2 2 1\n1 1 1 1\n\u003c/pre\u003e"}},{"title":"Sample Output 2","value":{"format":"MD","content":"\u003ch3\u003e\u003c/h3\u003e\n\u003cpre\u003e3\n\u003c/pre\u003e \n\u003cp\u003e可能有多条航线连接同一对星球,而一条航线从一个星球到同一个星球.\u003c/p\u003e"}},{"title":"Sample Input 3","value":{"format":"MD","content":"\u003ch3\u003e\u003c/h3\u003e\n\u003cpre\u003e4 2\n1 2 3 4\n3 4 5 6\n\u003c/pre\u003e"}},{"title":"Sample Output 3","value":{"format":"MD","content":"\u003ch3\u003e\u003c/h3\u003e\n\u003cpre\u003e-1\n\u003c/pre\u003e \n可能没有从星球 1 到星球 N 的路径。"}},{"title":"Sample Input 4","value":{"format":"MD","content":"\u003ch3\u003e\u003c/h3\u003e\n\u003cpre\u003e6 9\n1 1 0 0\n1 3 1 2\n1 5 2 3\n5 2 16 5\n2 6 1 10\n3 4 3 4\n3 5 3 10\n5 6 1 100\n4 2 0 110\n\u003c/pre\u003e"}},{"title":"Sample Output 4","value":{"format":"MD","content":"\u003ch3\u003e\u003c/h3\u003e\n\u003cpre\u003e20\n\u003c/pre\u003e"}}]}