{"problem":{"name":"Train","description":{"content":"In the Republic of AtCoder, there are $N$ cities numbered $1$ through $N$ and $M$ railroads numbered $1$ through $M$. Railroad $i$ connects City $A_i$ and City $B_i$ bidirectionally. At time $0$, $K_i","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc192_e"},"statements":[{"statement_type":"Markdown","content":"In the Republic of AtCoder, there are $N$ cities numbered $1$ through $N$ and $M$ railroads numbered $1$ through $M$.\nRailroad $i$ connects City $A_i$ and City $B_i$ bidirectionally. At time $0$, $K_i$, and all subsequent multiples of $K_i$, a train departs from each of these cities and head to the other city. The time each of these trains takes to reach the destination is $T_i$.\nYou are now at City $X$. Find the earliest time you can reach City $Y$ when you start the journey by taking a train that departs City $X$ not earlier than time $0$. If City $Y$ is unreachable, report that fact.  \nThe time it takes to transfer is ignorable. That is, at every city, you can transfer to a train that departs at the exact time your train arrives at that city.\n\n## Constraints\n\n*   $2 \\leq N \\leq 10^5$\n*   $0 \\leq M \\leq 10^5$\n*   $1 \\leq X,Y \\leq N$\n*   $X \\neq Y$\n*   $1 \\leq A_i,B_i \\leq N$\n*   $A_i \\neq B_i$\n*   $1 \\leq T_i \\leq 10^9$\n*   $1 \\leq K_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$ $X$ $Y$\n$A_1$ $B_1$ $T_1$ $K_1$\n$\\vdots$\n$A_M$ $B_M$ $T_M$ $K_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc192_e","tags":[],"sample_group":[["3 2 1 3\n1 2 2 3\n2 3 3 4","7\n\nFirst, you take Railroad $1$ at time $0$ and go from City $1$ to City $2$. You arrive at City $2$ at time $2$.\nThen, you take Railroad $2$ at time $4$ and go from City $2$ to City $3$. You arrive at City $3$ at time $7$.\nThere is no way to reach City $3$ earlier."],["3 2 3 1\n1 2 2 3\n2 3 3 4","5\n\nFirst, you take Railroad $2$ at time $0$ and go from City $3$ to City $2$. You arrive at City $2$ at time $3$.\nThen, you take Railroad $1$ at time $3$ and go from City $2$ to City $1$. You arrive at City $1$ at time $5$."],["3 0 3 1","\\-1"],["9 14 6 7\n3 1 4 1\n5 9 2 6\n5 3 5 8\n9 7 9 3\n2 3 8 4\n6 2 6 4\n3 8 3 2\n7 9 5 2\n8 4 1 9\n7 1 6 9\n3 9 9 3\n7 5 1 5\n8 2 9 7\n4 9 4 4","26"]],"created_at":"2026-03-03 11:01:14"}}