## Traffic Lights

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 16M

Author:
Problem type

Jim-Bob lives in a strange city where the streets don't necessarily run NS or EW. Instead the streets run seemingly at random, sometimes crossing over each other by bridges, and intersecting with one another at exactly intersections. Each intersection consists of some streets coming together, as well as a traffic light.

Street starts at intersection , and ends at a different intersection , going through no other intersections in between. It takes minutes to travel down street (this number is derived from the length, the average pothole size, and the amount of roadkill). Each road can be travelled in either direction in the same amount of time.

The traffic lights in this city are also strange. First of all, each one only alternates between green and red. Each light also cycles through these colours at a different rate – the traffic light located at intersection stays green for minutes, then stays red for minutes, then goes back to green, and so on.

Jim-Bob always obeys the law, and will never run a red light. If he arrives at an intersection while the light is green, he can pass right through it. Otherwise, he must wait there until the light turns green. If he gets to an intersection just as the traffic light is turning red, he must wait. It takes no time to drive through an intersection, so the light will never turn red on him as he drives through.

Jim-Bob starts at his house, also known as intersection . As soon as he leaves his house, all the traffic lights turn green, starting their green-red-green cycle. He wishes to drive to Billy-Bob's house (which is right at intersection ) as fast as possible. Neither the starting nor the finishing intersection have traffic lights, so their and will be given as . Find the minimum number of minutes Jim-Bob can take to drive from his house to Billy-Bob's.

#### Input Specification

integers – and .
The next lines contain integers each – , , and .
The next lines contain integers each – , and .

#### Output Specification

A single integer – the minimum number of minutes it takes to drive from Jim-Bob's house to Billy-Bob's. It will always be possible to do this.

#### Sample Input

7 6
1 2 4
1 3 1
3 5 2
2 4 2
2 5 6
5 4 2
5 6 10
0 0
5 5
1 20
2 5
10 2
0 0

#### Sample Output

19

#### Explanation

The city looks something like this (Jim-Bob's best route is shown in red):

Jim-Bob can drive to intersection ( min), drive on to intersection ( min), wait for the green light ( min), drive down to intersection ( min), and finally drive to Billy-Bob's house ( min). This is a total of minutes.

Note: The traffic light at intersection only stays green for minute, which means that Jim-Bob would just miss it if he drove directly there. On the other hand, he makes the green lights as intersections and just in time, as they turn red minute after he passes.