Young, Poor and Busy

Ken and Keiko are students buried in part time jobs, so they have neither time nor money to spare. Ken lives in Hakodate, Keiko lives in Tokyo. They want to see each other, but each has to be back at work the same day, and the fare matters. Find the cheapest way for the two of them to meet.

Ken starts in Hakodate and Keiko starts in Tokyo. Both know the time and the fare of every train, and they may meet in any city, including the cities they live in. Neither of them may depart before 08:00, and both must be back in their own city by 18:00. A transfer takes no time, so a traveler may board the next train in the same minute he or she arrives. They want to spend at least 30 minutes together in one city.

A timetable can hold up to 100 cities and up to 2000 direct connections. Building every possible itinerary one by one does not finish inside the time limit.

The input is a sequence of data sets.

The first line of a data set holds one integer, the number of connections in the timetable. It is at most 2000.

The following lines hold one connection each, in this format.

StartCity HH:MM ArrivalCity HH:MM price

A city name is at most 16 letters long and only its first letter is upper case. Departure and arrival times are written with two digits for the hour and two digits for the minute, separated by a colon, and range from 00:00 to 23:59. The arrival time is strictly later than the departure time. The price of one connection is an integer between 1 and 10000. Fields are separated by spaces.

A line holding a single zero ends the input.

For each data set print the lowest possible total fare on its own line. This is the sum of the fares of every connection the two of them use.

Print 0 for a data set that has no way for them to meet.