I - 信号待ち

コンテスト時間: 2014-11-09 15:30:00+0900 ~ 2014-11-09 17:00:00+0900 (90分)

I - 信号待ち解説

実行時間制限: 2 sec / メモリ制限: 256 MB

陸運企業陸道社の社員である amylase 伯爵さんは、荷物を届けるためにとある街を訪れました。この街は、n 個の交差点と、交差点同士を結ぶ m 本の道路でできており、交差点には 1 から n までの番号がつけられています。

それぞれの交差点には信号機が 1 つずつ存在し、各信号機は青または赤の 2 つの状態を持ちます。時刻 t = 0, 1, 2, ... における交差点 i の信号機の状態は、パラメータ a_i, b_i, c_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 の信号機は時刻 4 にはじめて青になり、そこから 4 秒かけて 2 に移動すればよい。