Public Transit

You are standing somewhere in the city and want to reach one particular bus stop as early as possible.

You know which stops you can walk to from where you are and how long each walk takes, and you have a list of one way bus routes. Each route gives the stop where you board, the minute the bus leaves that stop, the stop the route leads to, and how long the ride takes.

The clock starts at minute 0. You catch a bus when you are at its boarding stop no later than the minute it leaves, and you may wait at a stop for as long as you want. Walking happens once, from your starting location to a stop, so you cannot walk from one stop to another.

Find the itinerary that reaches the destination stop at the earliest minute.

The first line has $W$, the number of stops within walking distance of your current location.

Each of the next $W$ lines has a five digit stop number and the number of minutes it takes you to walk there.

The next line has $R$, the number of bus routes.

Each of the next $R$ lines has the stop number where you board, the minute the bus leaves that stop counted from now, the stop number the route leads to, and the number of minutes the ride takes.

The next line has a single five digit stop number, your destination.

The input holds several test cases in a row and ends with a line that contains only 0 in place of $W$.

Print one line for each test case.

If the destination cannot be reached, print Unreachable.

Otherwise print the itinerary in this form.

ETA: X minute(s) Take stop: S1 S2 ... SN

$X$ is the minute you arrive at the destination, and $S_1$ through $S_N$ are the stops in the order you visit them. $S_1$ is the stop you walk to and $S_N$ is the destination. Print minute(s) exactly like that whatever the number is. Walking straight to the destination counts as an itinerary with one stop.

When several itineraries arrive at the same minute, print the one with the fewest stops. When they also have the same number of stops, compare the stop numbers from the front and print the one whose first differing stop number is smaller.