Traffic Lights

The city of Kenosha has $M$ roads, numbered $1 \ldots M$, that connect $N$ junctions, numbered $1 \ldots N$. No two roads connect the same pair of junctions, and no road connects a junction to itself. The integer travel time $T_{ij}$ between junctions $i$ and $j$ is the same in both directions, so $T_{ij} = T_{ji}$.

Each junction has a single traffic light that shows one of two colors, blue or purple. Each light alternates periodically: it stays blue for a fixed number of seconds, then purple for another fixed number of seconds, then repeats. You may set off down the road between two junctions only if, at the exact instant you leave one junction for the other, the lights at both junctions show the same color. The two lights do not have to stay the same color for the rest of the trip.

If a vehicle reaches a junction at the exact instant its light switches, the new color applies. Vehicles may wait at a junction as long as they like. For each junction $i$ you are given its blue duration $DB_i$, its purple duration $DP_i$, its initial color $C_i$ (B for blue or P for purple), and the remaining time $R_i$ before that initial color first changes.

Starting at time $0$ at a source junction $S$, find the minimum time needed to reach a destination junction $D$ ($D \ne S$).

Constraints: $2 \le N \le 300$, $1 \le M \le 14{,}000$, $1 \le T_{ij} \le 100$, $1 \le DB_i \le 100$, $1 \le DP_i \le 100$, $1 \le R_i \le 100$, $1 \le S, D \le N$.

Worked example. Consider four junctions and five roads, where a vehicle wants to travel from junction 1 to junction 4.

Roads (with travel times): 1-2 (4), 1-3 (40), 2-3 (75), 2-4 (76), 3-4 (77).

The minimum time is 127, along the path 1 -> 2 -> 4:

• Junction 1 starts blue while junction 2 is purple, so the vehicle waits 2 seconds until junction 1 also turns purple, then drives 4 seconds to junction 2, arriving at time 6.
• At time 6 junction 2 turns blue, but junction 4 stays purple for 32 more seconds. After those 32 seconds junction 2 turns purple exactly as junction 4 turns blue, so they still differ. The vehicle waits 13 more seconds until junction 2 turns blue; now both are blue, so it drives 76 seconds to junction 4.
• Total time: $2 + 4 + 32 + 13 + 76 = 127$ seconds.

• Line 1: two space-separated integers $S$ and $D$.
• Line 2: two space-separated integers $N$ and $M$.
• Lines 3 to $N+2$: line $i+2$ describes junction $i$ with one character and three integers separated by single spaces: $C_i$, $R_i$, $DB_i$, and $DP_i$.
• Lines $N+3$ to $N+M+2$: line $N+2+k$ describes road $k$ with three integers $i$, $j$, and $T_{ij}$.

• Line 1: a single integer, the time of a minimum-time path from the source junction to the destination junction. If no path exists, output $0$.