AT_abc192_e [ABC192E] Train

在 AtCoder 国有 $N$ 个城市，编号为 $1$ 到 $N$，以及 $M$ 条铁路，编号为 $1$ 到 $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$。

### 限制条件 - $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$ - 所有输入均为整数 ### 样例解释 1 首先，在时刻 $0$ 乘坐第 $1$ 条铁路，从城市 $1$ 前往城市 $2$，于时刻 $2$ 到达城市 $2$。随后，在时刻 $4$ 乘坐第 $2$ 条铁路，从城市 $2$ 前往城市 $3$，于时刻 $7$ 到达城市 $3$。没有比这更早到达城市 $3$ 的方法。 ### 样例解释 2 首先，在时刻 $0$ 乘坐第 $2$ 条铁路，从城市 $3$ 前往城市 $2$，于时刻 $3$ 到达城市 $2$。随后，在时刻 $3$ 乘坐第 $1$ 条铁路，从城市 $2$ 前往城市 $1$，于时刻 $5$ 到达城市 $1$。 由 ChatGPT 4.1 翻译