Traffic Light Scheduling

Kenosha, the city nearest Farmer John, consists of N junctions and M bidirectional roads. Each road connects two distinct junctions and its travel time is given. At each junction there is a traffic light that alternates between blue and purple.

For junction i, you are given:

• An initial color C_i (either 'B' for blue or 'P' for purple) and a remaining time R_i (in seconds) during which the light shows that color.
• The full duration for blue (D_B[i]) and purple (D_P[i]) phases. After the initial phase the light will switch to the opposite color for its full duration, and then alternate between the two colors.

A vehicle may only start travelling along a road at a time when the departure junction and the destination junction have the same color. (It is not required that the lights remain the same color during travel.) If a vehicle arrives at a junction exactly when the light is switching, the new color applies immediately. Vehicles are allowed to wait at the junctions.

Given a source junction S and a destination junction D, determine the minimum time needed to travel from S to D.

Notes:

• The travel time on each road is given and is the same in both directions.
• No two roads connect the same pair of junctions and no road connects a junction to itself.

Example:

Input:
4 5 1 4
1: initial B, R=2, DB=16, DP=99
2: initial P, R=6, DB=32, DP=13
3: initial P, R=2, DB=87, DP=4
4: initial P, R=38, DB=96, DP=49
Roads:
1 2 4
1 3 40
2 3 75
2 4 76
3 4 77
The minimum travel time is 127 seconds using path 1-2-4.
Detailed Explanation:
At time 0 at junction 1 the light is blue but junction 2 is purple, so the vehicle waits 2 seconds at junction 1. Then, it travels from 1 to 2 in 4 seconds. At time 6, junction 2 turns blue while junction 4 is not blue yet, so the vehicle waits until time 32 later when both junctions are blue, waits an additional 13 seconds for junction 2 to become blue again, and then travels the road taking 76 seconds.
Total time = 2 + 4 + 32 + 13 + 76 = 127 seconds.

</p>

inputFormat

The first line contains four integers: N, M, S, and D, representing the number of junctions, the number of roads, the source junction, and the destination junction respectively.

The next N lines each contain the description of a junction. Each line contains a character C (either 'B' or 'P'), and three integers R, DB, and DP, representing the initial color, the remaining time for the initial color, the duration of the blue light, and the duration of the purple light, respectively.

The following M lines each contain three integers: u, v, and T, indicating that there is a bidirectional road connecting junctions u and v with travel time T.

outputFormat

Output a single integer representing the minimum time required to get from junction S to junction D.

sample

4 5 1 4
B 2 16 99
P 6 32 13
P 2 87 4
P 38 96 49
1 2 4
1 3 40
2 3 75
2 4 76
3 4 77

127