Trip Routing

Your employer, the California Car Club (CCC), has decided to offer a trip-routing service to its members. Write a program that reads a list of (departure point, destination point) pairs and computes the shortest route between the two cities of each pair. For every trip, print a report that itemises each city the route passes through, together with the route names and the mileage of each leg.

The input has two parts.

The first part is a map given as a list of highway segments. Each segment is one line of four comma-separated fields:

• Fields 1 and 2: the names of the two cities at the ends of the segment (1–20 characters each).
• Field 3: the route name (1–10 characters).
• Field 4: the distance in miles between the two endpoints, a positive integer.

Every highway segment may be travelled in either direction. The list of segments is terminated by an empty line.

The second part is a list of (departure point, destination point) pairs, one per line, written as departure,destination. Every city named here also appears in the map, and a path always connects the two cities. This list runs to the end of the input.

Print one report for each pair, in the order the pairs are given.

Each report consists of:

• a header line and a line of dashes;
• one line for every leg of the shortest route, showing the leg's start city, end city, route name and mileage;
• a line of dashes under the Miles column, followed by a Total line giving the total mileage.

The columns are fixed width and separated by a single space: From and To are 20 characters wide and left-justified, Route is 10 characters wide and left-justified, and Miles is 5 characters wide and right-justified.

Two blank lines precede each report, except that a single blank line precedes the first report.

There are no extraneous blanks in the input. The map has at most 100 cities and at most 200 highway segments, and the total length of each shortest route fits in a 16-bit integer. For every pair, the shortest route is unique.