{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"Input 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$"},{"iden":"sample input 1","content":"3 2 1 3\n1 2 2 3\n2 3 3 4"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"3 2 3 1\n1 2 2 3\n2 3 3 4"},{"iden":"sample output 2","content":"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$."},{"iden":"sample input 3","content":"3 0 3 1"},{"iden":"sample output 3","content":"\\-1"},{"iden":"sample input 4","content":"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"},{"iden":"sample output 4","content":"26"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}