Problem Statement

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$, 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$.

You 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. The 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.

Constraints

• $2 \leq N \leq 10^5$
• $0 \leq M \leq 10^5$
• $1 \leq X,Y \leq N$
• $X \neq Y$
• $1 \leq A_i,B_i \leq N$
• $A_i \neq B_i$
• $1 \leq T_i \leq 10^9$
• $1 \leq K_i \leq 10^9$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M X Y
A_1 B_1 T_1 K_1
\vdots
A_M B_M T_M K_M

Output

Print the earliest possible time you can reach City $Y$. If City $Y$ is unreachable, print -1 instead.