E - 列车

分数：500分

问题描述

在AtCoder共和国中，有$N$个从$1$到$N$编号的城市和$M$个从$1$到$M$编号的铁路。

铁路$i$双向连接了城市$A_i$和城市$B_i$。在时间$0$，$K_i$，以及所有后续的$K_i$的倍数时刻，每个城市都会有一辆列车从该城市出发到达另一个城市。这些列车到达目的地所需的时间是$T_i$。

你现在位于城市$X$。找出你可以在从城市$X$出发的列车出发时间不早于$0$的情况下到达城市$Y$的最早时刻。如果无法到达城市$Y$，请报告这个事实。
可忽略换乘所需的时间。也就是说，在每个城市，你可以在你的列车到达该城市的正好时刻换乘。

约束

• $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$
• 输入中的所有数值均为整数。

输入

从标准输入读入以下格式的输入：

$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