U169611.[ABC192E] Train

某国有 $N$ 座城市，编号 $1$ 到 $N$，之间有 $M$ 条双向列车线路。第 $i$ 条线路连接城市 $A_i$ 与 $B_i$，单程耗时 $T_i$，并且只在时刻为 $K_i$ 的倍数时发车（即时刻 $0, K_i, 2K_i, 3K_i, \cdots$）。

如果你在时刻 $t$ 到达某城市，想搭乘一条 $K$ 值为 $K_i$ 的线路，需要等到不早于 $t$ 的最近一个 $K_i$ 的倍数才能发车，即等待到时刻 $\lceil t / K_i \rceil \times K_i$，到达对面城市的时刻为该发车时刻加上 $T_i$。

你在时刻 $0$ 从城市 $X$ 出发，求最早到达城市 $Y$ 的时刻；如果无法到达，输出 $-1$。

第一行四个整数 $N, M, X, Y$。
接下来 $M$ 行，每行四个整数 $A_i, B_i, T_i, K_i$，表示一条连接 $A_i$ 与 $B_i$ 的双向线路，单程耗时 $T_i$，发车间隔 $K_i$。

一行一个整数，表示从城市 $X$ 最早到达城市 $Y$ 的时刻；若无法到达，输出 $-1$。

数据范围：$2 \le N \le 10^5$，$1 \le M \le 10^5$，$1 \le T_i, K_i \le 10^9$。

样例说明：时刻 $0$ 从城市 $1$ 乘坐第 $1$ 条线路（$K=3$，时刻 $0$ 恰为发车时刻），耗时 $10$，于时刻 $10$ 到达城市 $2$；再乘坐第 $2$ 条线路（$K=2$，时刻 $10$ 恰为发车时刻），耗时 $5$，于时刻 $15$ 到达城市 $3$。直接乘坐第 $3$ 条线路则需要到时刻 $80$ 才能到达，不如前者。