分数: 500 点
问题陈述
在AtCoder共和国,有 N 城市编号 1 通过 N 和 M 铁路编号 1 通过 M.
铁路 i 连接城市 A_i 和城市 B_i 双向。时 0, K_i,以及所有后续的倍数 K_i,一列火车从这些城市中的每一个城市出发,前往另一个城市。每趟列车到达目的地所需的时间为 T_i.
您现在位于城市 X。查找您可以到达城市的最早时间 Y 当您乘坐从城市出发的火车开始旅程时 X 不早于时间 0。如果城市 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
首先,你乘坐铁路 1 时间 0 从城市出发 1 前往城市 2。您到达城市 2 时间 2.
然后,你乘坐铁路 2 时间 4 从城市出发 2 前往城市 3。您到达城市 3 时间 7.
没有办法到达城市 3 早些时候。
示例输入 2
3 2 3 1 1 2 2 3 2 3 3 4
示例输出 2
5
首先,你乘坐铁路 2 时间 0 从城市出发 3 前往城市 2。您到达城市 2 时间 3.
然后,你乘坐铁路 1 时间 3 从城市出发 2 前往城市 1。您到达城市 1 时间 5.
示例输入 3
3 0 3 1
示例输出 3
-1
示例输入 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