Electric Car Rally

ElecCarCo wants to show that electric cars are practical, so it sponsors a cross country road rally. The course has $n$ charging stations numbered $0$ to $n-1$, and a car can stop at any of them to charge its battery.

The rally can run over several days. A full battery holds $240$ minutes of driving, and every minute of driving costs two minutes plugged into a charger. Charge builds up in proportion to the time spent plugged in, so $w$ minutes on a charger buys $w/2$ minutes of driving, up to the limit of $240$ minutes. Every car leaves at noon on the first day with a full battery, and a car may stay at a station as long as it likes, even after the battery is full. A car cannot enter a road when the driving time left in its battery is less than the travel time of that road.

Roads exist only between certain pairs of stations. Traffic, road conditions, HOV lanes and similar factors make the travel time on a road depend on the time of day at which a car enters it. Every road is two way, and the same conditions apply in both directions.

The winner is the first car to reach station $n-1$ after starting from station $0$. Apart from the start and the finish there are no restrictions: a car may pass through the other stations in any order, and it does not have to visit all of them.

Write a program that finds the earliest time a car can reach the final station, measured in minutes elapsed since the rally started.

The input holds several test cases. Each test case begins with a line holding $n$ ($1 \le n \le 500$), the number of stations, and $m$ ($1 \le m \le 1000$), the number of road segments.

Then come $m$ blocks, one per road segment. A block begins with a line holding two integers $a$ and $b$ ($0 \le a, b \le n-1$, $a \ne b$), the two stations joined by that segment. The segment is undirected, so a car can drive from $a$ to $b$ and from $b$ to $a$.

After that come one to twenty travel lines. Each travel line holds three integers Start, Stop ($0 \le \text{Start} < \text{Stop} \le 1439$) and Time ($0 < \text{Time} < 1000$). Start and Stop are times of day in minutes after midnight, and Time is the number of minutes the segment takes when a car enters it at any moment in $[\text{Start}, \text{Stop}]$. The first travel line of a block has Start equal to $0$, and the last one has Stop equal to $1439$. The lines are given in increasing order of time and every line after the first starts one minute after the previous line stops, so the lines of a block cover the whole day from 00:00 to 23:59.

The input ends with a line holding two zeros. Every test case describes a course that a car can finish.

For each test case, print the smallest number of minutes needed to finish the rally as a single integer on its own line. Print nothing else, and leave no blank line between answers.