Shortest Travel Time

You are given a set of directed routes between cities. Each route is characterized by a departure city, a destination city, and the travel time between them. You are also given a set of queries asking for the shortest travel time from a given start city to an end city.

For each query, if the start and end cities are the same, the answer is 0. Otherwise, you must determine the minimum total travel time from the start city to the destination using the available routes. If no route exists, output NO ROUTE.

The shortest travel time between two cities, if a route exists, is given by:

$$d(u,v)=\min_{\text{path }P \ from\ u \ to\ v} \sum_{e \in P} \text{weight}(e)$$

inputFormat

The input is read from stdin and has the following format:

1. An integer R representing the number of routes.
2. R lines follow, each line contains a departure city (string), a destination city (string), and a travel time (integer) separated by spaces.
3. An integer Q representing the number of queries.
4. Q lines follow, each line consists of two strings: the start city and the destination city, separated by a space.
5. A terminating line containing a single 0 which should be ignored.

outputFormat

For each query, print the shortest travel time on a new line. If there is no possible route, print NO ROUTE.

4
A B 120
B C 150
A C 300
C D 80
3
A C
A D
B A
0

270
350
NO ROUTE