{"problem":{"name":"Rush Hour 2","description":{"content":"The Republic of AtCoder has $N$ cities and $M$ roads. The cities are numbered $1$ through $N$, and the roads are numbered $1$ through $M$. Road $i$ connects City $A_i$ and City $B_i$ bidirectionally. ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc204_e"},"statements":[{"statement_type":"Markdown","content":"The Republic of AtCoder has $N$ cities and $M$ roads.\nThe cities are numbered $1$ through $N$, and the roads are numbered $1$ through $M$. Road $i$ connects City $A_i$ and City $B_i$ bidirectionally.\nThere is a rush hour in the country that peaks at time $0$. If you start going through Road $i$ at time $t$, it will take $C_i+ \\left\\lfloor \\frac{D_i}{t+1} \\right\\rfloor$ time units to reach the other end. ($\\lfloor x\\rfloor$ denotes the largest integer not exceeding $x$.)\nTakahashi is planning to depart City $1$ at time $0$ or some **integer time** later and head to City $N$.\nPrint the earliest time when Takahashi can reach City $N$ if he can stay in each city for an **integer number of time units**. It can be proved that the answer is an integer under the Constraints of this problem.\nIf City $N$ is unreachable, print `-1` instead.\n\n## Constraints\n\n*   $2 \\leq N \\leq 10^5$\n*   $0 \\leq M \\leq 10^5$\n*   $1 \\leq A_i,B_i \\leq N$\n*   $0 \\leq C_i,D_i \\leq 10^9$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$ $C_1$ $D_1$\n$\\vdots$\n$A_M$ $B_M$ $C_M$ $D_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc204_e","tags":[],"sample_group":[["2 1\n1 2 2 3","4\n\nWe will first stay in City $1$ until time $1$. Then, at time $1$, we will start going through Road $1$, which will take $2+\\left\\lfloor \\frac{3}{1+1} \\right\\rfloor = 3$ time units before reaching City $2$ at time $4$.\nIt is impossible to reach City $2$ earlier than time $4$."],["2 3\n1 2 2 3\n1 2 2 1\n1 1 1 1","3\n\nThere may be multiple roads connecting the same pair of cities, and a road going from a city to the same city."],["4 2\n1 2 3 4\n3 4 5 6","\\-1\n\nThere may be no path from City $1$ to City $N$."],["6 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","20"]],"created_at":"2026-03-03 11:01:14"}}