问题描述

陆运企业陆道社的员工amylase伯爵要去一个城市送货。这个城市由$n$个交叉点和$m$条道路组成，每个交叉点都有编号从1到n。

每个交叉点都有一个交通信号灯，每个信号灯有两种状态：红色和绿色。对于时刻$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秒内通过。

现在，当amylase伯爵在时刻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$

• 第一行包含4个整数$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$条道路需要$t_i$秒从交叉点$x_i$移动到$y_i$。
• 提供的图是连通的，并且保证没有自环和重复边。

输出

输出从交叉点$s$到交叉点$d$的最短所需时间。

输出最后一行后换行，不包含额外字符或空行。

输入示例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