問題文
陆路运输公司陆道社的员工淀粉酶伯爵前往某城镇运送包裹。这座城市是 连接n 路口和路口 m 它是由真实的道路组成,在交叉路口有 它们的编号最大为 1 到 n 。
每个十字路口都有一个红绿灯。 1 每个交通灯都是蓝色或红色。 2 它有两种状态。时间 t = 0, 1, 2, ... 处的交叉路口 i 中交通灯的状态由参数确定 a_i, b_i, c_i 确定如下。
- 第一 c_i 秒,即 t = 0, 1, ..., c_{i}-1 为红色
- 然后, a_i 第二个蓝色和 b_i 秒红色重复
颜色从蓝色变为红色的时间(例如 t = c_i + a_i ),交通灯为红色,由红变绿的时间(例如: 请注意, t = c_i 时交通灯为绿色。
无论交通灯状态如何,您都可以到达每个路口,但只有在交通灯为绿色时才能从该路口出发。此外,除去红绿灯的等待时间,十字路口 您可以在 0 秒内完成它。
现在,是时候计算淀粉酶了。 0 处的交叉点 当您到达 s 时,前往十字路口 求前往 d 所需的最短时间。
入力
输入按以下格式给出。
n m s d a_1 b_1 c_1 ... a_n b_n c_n x_1 y_1 t_1 ... x_m y_m t_m
- 1 行包含一个表示交叉点数量的整数。 n (2 \leq n \leq 100{,}000), 表示道路数量的整数 m (1 \leq m \leq min(n(n-1)/2, 10^5)), 代表起点交集的整数 s (1 \leq s \leq n)和一个表示目标点交点的整数 d (1 \leq d \leq n)。 来自行
- s \neq d 有保证。
- 继续 n 行提供有关每个十字路口交通灯的信息。
- a_i, b_i, c_i (1 \leq a_i, b_i, c_i \leq 1{,}000{,}000{,}000) 是 第i 个十字路口的红绿灯是 c_i 秒为红色,然后 a_i 第二个蓝色和 b_i 表示重复第二个红色。
- 继续 m 行提供有关每条道路的信息。
- x_i, y_i (1 \leq x_i, y_i\leq n)和 t_i (0 \leq t_i \leq 1{,}000{,}000{,}000) 是 第i 路口 在 x_i 和 y_i 之间移动 这意味着需要 t_i 秒。
- 给定的图是连通的,并且保证不包含自边或重边。
出力
交差点 s 到交叉路口 移动到 d 所需的最短时间 1 按行输出。
在末尾使用换行符,并且不要包含不必要的字符或空行。
入力例1
2 1 1 2 3 3 4 9 9 9 1 2 4
出力例1
8
作为起点的交叉路口 1 红绿灯时间到了 它首先在 4 中变成蓝色,然后从那里开始 4 需要几秒钟 只需移至 2 。
入力例2
4 4 4 2 2 4 8 9 9 9 2 8 4 3 3 3 1 2 8 1 4 6 2 3 6 3 4 3
出力例2
17