Problem Description

Mr. Earl amylase, an employee of the land transport company Rikudou, visited a certain town to deliver packages. This town consists of $ n $ intersections and $ m $ roads connecting these intersections, with each intersection numbered from $ 1 $ to $ n $.

Each intersection has one traffic light, which can be in one of two states: green or red. The state of the traffic light at intersection $ i $ at time $ t = 0, 1, 2, ... $ is determined by parameters $ a_i $, $ b_i $, and $ c_i $ as follows:

• For the first $ c_i $ seconds, i.e., $ t = 0, 1, ..., c_i-1 $, the light is red.
• Afterwards, it alternates between $ a_i $ seconds of green and $ b_i $ seconds of red.

Note that the light is red at the moment it switches from green to red (e.g., at $ t = c_i + a_i $) and green at the moment it switches from red to green (e.g., at $ t = c_i $).

Each intersection can be arrived at regardless of the state of its traffic light, but it can only be departed from when the traffic light is green. Also, intersections can be passed through in $ 0 $ seconds, excluding waiting time due to traffic lights.

Given that Mr. Earl amylase is at intersection $ s $ at time $ 0 $, find the minimum time required to travel from intersection $ s $ to intersection $ d $.

Input Format

The input is given in the following format:

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

• The first line contains integers $ 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$), and $ d $ ($1 \leq d \leq n$), representing the number of intersections, the number of roads, the starting intersection, and the destination intersection, respectively.
• It is guaranteed that $s \neq d$.
• The next $ n $ lines contain information about the traffic lights at each intersection.
• $ a_i, b_i, c_i $ ($1 \leq a_i, b_i, c_i \leq 1,000,000,000$) indicate that the traffic light at the $ i $-th intersection is red for the first $ c_i $ seconds and then alternates between $ a_i $ seconds of green and $ b_i $ seconds of red.
• The next $ m $ lines contain information about each road.
• $ x_i, y_i $ ($1 \leq x_i, y_i \leq n$) and $ t_i $ ($0 \leq t_i \leq 1,000,000,000$) indicate that it takes $ t_i $ seconds to travel between intersections $ x_i $ and $ y_i $ via the $ i $-th road.
• The given graph is connected and does not contain self-loops or multiple edges.

Output Format

Output the minimum time required to travel from intersection $ s $ to intersection $ d $ in one line.

End with a newline and do not include any extra characters or blank lines.

Sample Input and Output

Sample Input #1

2 1 1 2
3 3 4
9 9 9
1 2 4

Sample Output #1

8

Sample Input #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

Sample Output #2

17

Notes/Hints

Sample Explanation 1

The traffic light at the starting intersection $ 1 $ turns green for the first time at time $ 4 $, and it takes $ 4 $ seconds to travel to intersection $ 2 $.

见题面 Input 部分

见题面 Output 部分