题面翻译

给定 $N$ 个编号为 $1$ 至 $N$ 的城市以及 $M$ 条铁路。

第 $i$ 条铁路连接城市 $A_i$ 和 $B_i$，每当时间为 $K_i$ 的倍数时会同时、分别从 $A_i$ 和 $B_i$ 发出开往对方的列车，列车从出发至到达花费 $T_i$ 时间。

开始时你在城市 $X$，输出你到达城市 $Y$ 的最早时间。若无法到达，输出 -1。

忽略转车所需要的时间。即，当你 $T$ 时刻到达某个城市时，可以立刻乘坐 $T$ 时刻从这个城市发出的列车。

输入格式

第一行四个整数 $N,M,X,Y$

接下来 $M$ 行每行四个整数 $A_i,B_i,T_i,K_i$

输出格式

输出到达城市 $Y$ 的最小时间，无法到达输出 -1

3 2 1 3
1 2 2 3
2 3 3 4

7

3 2 3 1
1 2 2 3
2 3 3 4

5

3 0 3 1

-1

9 14 6 7
3 1 4 1
5 9 2 6
5 3 5 8
9 7 9 3
2 3 8 4
6 2 6 4
3 8 3 2
7 9 5 2
8 4 1 9
7 1 6 9
3 9 9 3
7 5 1 5
8 2 9 7
4 9 4 4

26

提示

• $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$
• 入力は全て整数

Sample Explanation 1

首先，您在时间 $0$ 乘坐铁路 $1$ ，从城市 $1$ 前往城市 $2$ 。您在时间 $2$ 到达城市 $2$ 。

然后，您在时间 $4$ 乘坐铁路 $2$，从城市 $2$ 前往城市 $3$。在时间 $7$ 到达城市 $3$ 。

无法提前到达城市 $3$ 。