Trip the Lights Fantastic

Bob works at the Traffic Commission for a medium-size town. He is in charge of monitoring the traffic lights in the city and dispatching repair crews when necessary. With a lot of free time, he tries to figure out the quickest way to make short trips between various points in the city. Bob knows the layout of the streets and the location and cycle times of every traffic light. To simplify things, he makes these assumptions:

1. All cars travel at the same top speed, and a car sitting at a red light takes 5 seconds to react and get up to speed. (That is, the car is essentially standing still for 5 seconds, then proceeds at top speed. Bob also assumes the light will not turn back to red during those 5 seconds.)
2. Each car approaches a light at full speed and either passes through it if it is green or yellow, or comes to an immediate stop if it is red. A car may pass through a light if it arrives exactly as the light turns green. A car must stop if it reaches the light exactly as the light turns red.
3. The time to make turns through a light is ignored. It is possible to travel between any two lights, though perhaps not directly.

Furthermore, no U-turns are allowed, and a route never revisits an intersection. Help Bob find minimum-time paths.

A light with green, yellow, and red durations $g$, $y$, $r$ has cycle length $g + y + r$. All lights begin their green period at time 0; during a cycle, seconds $[0, g)$ are green, $[g, g+y)$ are yellow, and $[g+y, g+y+r)$ are red, and then the cycle repeats.

The input contains several test cases. The first line of each test case has four positive integers $n$, $m$, $s$, and $e$, where $n$ ($2 \le n \le 100$) is the number of traffic lights (numbered $0$ through $n - 1$), $m$ is the number of roads between the lights, and $s$ and $e$ ($s \ne e$) are the start and end lights of the desired trip.

The next $n$ lines each have the form g y r, giving the number of seconds each light is green, then yellow, then red ($1 \le g, y, r \le 100$). The first of these lines is for light $0$, the second for light $1$, and so on.

The following $m$ lines each describe one road, in the form l1 l2 t, where l1 and l2 are the two lights the road connects and $t$ is the time in seconds to travel the road at full speed ($t \le 500$); add $5$ to this value to obtain the travel time when starting the road from a standstill. All roads are two-way.

At time $0$ all lights are just starting their green period and your car is at a standstill at light $s$. Because it takes 5 seconds to get going, you may assume $g + y$ is never less than or equal to $5$. The last test case is followed by a line containing 0 0 0 0, which ends the input.

For each test case, output a single line with the minimum time to travel from the start light to the end light, in the form mm:ss (minutes and seconds). If the number of seconds is less than 10, pad it with a leading zero (for example, output 4:05, not 4:5). If the number of minutes is less than 10, print just one digit (as in 4:05).