题号：NC273395
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
The road construction in City A consists of 
intersections with traffic lights (numbered from 
to 
) and 
bidirectional roads.
Here are the rules:
1. All vehicles travel at maximum speed.
2. Starting from 0 seconds, traffic lights at all intersections alternate between green, yellow, and red signals. When a vehicle arrives, it can pass if the light is green or yellow; otherwise, it must stop immediately. Specifically, if the light turns green at the moment of arrival, vehicles can pass. If the light turns red at the moment of arrival, vehicles cannot pass.
3. Each intersection's traffic light has three parameters
, representing the durations of green, yellow, and red lights, respectively. The transition of traffic lights does not consume time.
4. It takes 5 seconds for a vehicle to accelerate from a standstill to maximum speed. During this period, the vehicle's speed is 0. The transition of traffic lights during the acceleration process is not considered.
If a vehicle departs from intersection
at time 0, the task is to find the shortest time to reach intersection 
. It is guaranteed that any two intersections in City A can be reached through roads.
Here are the rules:
1. All vehicles travel at maximum speed.
2. Starting from 0 seconds, traffic lights at all intersections alternate between green, yellow, and red signals. When a vehicle arrives, it can pass if the light is green or yellow; otherwise, it must stop immediately. Specifically, if the light turns green at the moment of arrival, vehicles can pass. If the light turns red at the moment of arrival, vehicles cannot pass.
3. Each intersection's traffic light has three parameters
4. It takes 5 seconds for a vehicle to accelerate from a standstill to maximum speed. During this period, the vehicle's speed is 0. The transition of traffic lights during the acceleration process is not considered.
If a vehicle departs from intersection
输入描述:
The first line contains four integers, with the constraints
.
Following that, there are n lines, each with three integers, representing the three parameters of traffic lights at intersection
(where intersections are numbered from
to
). It's guaranteed that
, and
.
Then, there are m lines, each with, describing a road between intersections
and
with a transit time of
. Note that this time does not include the startup time; in other words, the total time including startup and transit is
. Roads are bidirectional, and it's guaranteed that
, and
.
Multiple test cases are expected, with the end indicated by. Each test case set contains at most 10 test cases.
输出描述:
For each dataset, output a line in the formatindicating the required time as
minutes and
seconds. If