Interstar Transport

By 2100, space travel will be a reality for the Milky Way (Solar Galaxy) residents. The Interstar Transport Travel agency operates scheduled direct space transports (flights) between some of the most popular planet destinations in the Milky Way. The cost of these scheduled direct transports are prede- termined in Galaro (Galaxy Currency unit) and are published in many different languages. For travel to planets that is not on the schedule, there are slower, yet free, space flights from the closest planet that is on the direct transport list. To help travelers plan their itinerary, the Interstar Transport wants to offer a mobile application that can find the best traveling option, based on the total cost of the direct transports on the itinerary. Given the starting and destination planets on the itinerary, find the sequence of direct transports that has the lowest total traveling cost. Output all the planets in sequence that one must pass through on this best route. If two or more routes exist with the same cost, then the route that goes through the least number of intermediate planets is considered a better route. There will always exist a unique best route for any of the given test cases. Technical Specification

1. The number of planets on the direct transport list is at most s, 1 ≤ s ≤ 26. The planets are labeled using capital letters of the English alphabets, i.e., “A”, “B”, “C”, . . ., “Z”, in no particular order.
2. The Interstar Transport operates at most p, 1 ≤ p ≤ 200, direct transports between planets. There is at most one (could be none) direct transport between any two distinct planets.
3. The cost of any transport is given as a natural number less than or equal to 100 Galaros. Input The first line of the input file contains two integers, s and p, separated by a space. The next p lines each contains two letters, ei and ej, followed by a natural number, dij, indicating that there exists a direct transport between planets ei and ej with a cost of dij. The next line contains an integer n ≤ 20, indicating the number of queries to follow. For each of the next n lines, each line contains two letters ek and em, indicating a user is looking for a best (lowest cost) way to get from planet ek to planet em. Output For each of the n queries in the input, output on one line the best route to take, in the sequence of starting planet, the intermediate planets in sequence along the route and the destination planet; all separated by one blank space. Sample Input 57 AB1 BC2 CD3 DE2 EA1 AD3 AC4

2/2 3 BD AD EC Sample Output BAD AD EABC