amylase 伯爵来到了某条街。这条街由 $n$ 个路口和连接这些路口的 $m$ 条道路构成。

每个路口都有一个红绿灯，每个红绿灯有红色和绿色两种状态。时间 $t=0,1,2,\dots$ 的十字路口 $i$ 的信号状态，根据如下参数 $a_i,b_i,c_i$ 决定：

• 最开始的 $c_i$ 秒，即 $t=0,1,\dots,c_i-1$ 时是红色；
• 然后重复 $a_i$ 秒的绿色和 $b_i$ 秒的红色。

注意：从绿色变为红色的时刻（例如，$t=c_i+a_i$ 时）信号是红色，从红色变为绿色的时刻（例如，$t=c_i$ 时）信号是绿色。

从路口 $u$ 通过一条道路走到路口 $v$ 与 $v$ 的信号灯的状态无关，但只有在 $u$ 的信号灯的状态为绿色时才能走过该条道路。此外，除红绿灯等待时间外，所有路口只需 0 秒即可通过。

道路是双向的，通过一条道路 $(x_i,y_i)$ 需要花费 $t_i$ 秒。

那么，当 amylase 伯爵在时刻 0 时位于路口 $s$ 时，请求出从路口 $s$ 出发抵达路口 $d$ 所需要的最短时间。

输入格式

第一行四个正整数 $n,m,s,d$。

第 $2$ 到第 $n+1$ 行，第 $i+1$ 行三个正整数分别表示 $a_i,b_i,c_i$。

第 $n+2$ 到第 $n+m+1$ 行，第 $n+1+i$ 行三个正整数分别表示 $x_i,y_i,t_i$。

输出格式

一行一个整数表示从 $s$ 到达 $d$ 所需的最短时间。

数据范围

$2 \le n \le 10^5,1 \le m \le \min(\frac{n(n-1)}{2},10^5),1 \le s,d \le n,s \neq d$。

$1 \le a_i,b_i,c_i,t_i \le 10^9,1 \le x_i,y_i \le n$。

保证不存在重边与自环。