题目描述

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

第 $i$ 条铁路双向连接了城市 $A_i$ 和城市 $B_i$。每当时间为 $0$、$K_i$ 或其后的 $K_i$ 的倍数时，一列列车便会从这些城市之一出发，前往另一个城市。每列火车到达目的地所需的时间为 $T_i$。

你现在位于城市 $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。

---

示例输入 1

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

示例输出 1

7

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

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

无法更早到达城市 $3$。

---

示例输入 2

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

示例输出 2

5

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

然后，你在时间 $3$ 乘坐铁路 $1$ 从城市 $2$ 前往城市 $1$。你在时间 $5$ 到达城市 $1$。

---

示例输入 3

3 0 3 1

示例输出 3

-1

无法到达城市 $Y$。

---

示例输入 4

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

示例输出 4

26