問題文

陸運企業陸道社の社員である amylase 伯爵さんは、荷物を届けるためにとある街を訪れました。この街は、$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$ 秒で通過することができます。

さて、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$

• $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