铁路时刻

题目描述

AtCoder 国有编号为 $1$ 到 $N$ 的 $N$ 个城市,以及编号为 $1$ 到 $M$ 的 $M$ 条铁路。

铁路 $i$ 连接城市 $A_i$ 和城市 $B_i$,每当时刻成为 $K_i$ 的倍数时,就会从两个城市分别向对方城市发车。这趟列车从出发到到达需要 $T_i$ 的时间。

你现在在城市 $X$。当你在时刻 $0$ 或之后乘上从城市 $X$ 出发的列车开始移动时,最早能在什么时候到达城市 $Y$?如果无法到达城市 $Y$,请报告这一情况。

另外,换乘所需时间可以忽略,因此在任何城市,都可以换乘与你所乘列车到达时刻同时发车的另一趟列车。

输入格式

输入按以下格式从标准输入给出:

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

输出格式

输出能够到达城市 $Y$ 的最早时刻。但是,如果无法到达城市 $Y$,则改为输出 -1。

样例

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

7

首先,在时刻 $0$ 乘坐铁路 $1$,从城市 $1$ 移动到城市 $2$。在时刻 $2$ 到达城市 $2$。

之后,在时刻 $4$ 乘坐铁路 $2$,从城市 $2$ 移动到城市 $3$。在时刻 $7$ 到达城市 $3$。

没有比这更早到达城市 $3$ 的方法。

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

5

首先,在时刻 $0$ 乘坐铁路 $2$,从城市 $3$ 移动到城市 $2$。在时刻 $3$ 到达城市 $2$。

之后,在时刻 $3$ 乘坐铁路 $1$,从城市 $2$ 移动到城市 $1$。在时刻 $5$ 到达城市 $1$。

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$
• 输入均为整数