Chico loves to drive, always in high speeds. Another Chico's love is Forró, a kind of music very popular in the Northeast Brazilian. But Chico's city doesn't have many Forró parties and he needs to travel to other cities if he wishes to go to a Forró party.
Chico, besides driving and Forró dancing, also likes computers and programming. As he is a very good programmer, he decides to make a program to calculate the best way to go from his city to a city where will have a Forró party. But, unfortunately, Chico needs to go out with his girlfriend and can not do the program, so he asked for your help.
But Chico's car has a problem with the brakes and he can not fix because if he does this he will not have money to buy the party's ticket and drink some beers. So you should find a route where Chico brakes only once, when he arrives in his destiny. Because he can not break, is dangerous pass by a city, so Chico should through the minimum number of cities in his travel.
The input file contains several input sets. The description of each set is given below:
Each set starts with one integer R (0 < R ≤ 5000), the number of roads. Next R lines describe the roads and consist of two cities name, where each city name has at most 30 characters, and V (0 < V ≤ 1000) the Chico's car velocity when Chico travels between the cities A and B. You can assume that A and B are not the same city and can exist more than one road between two cities. After this there is a line with two city names, the fist is the city where Chico lives and the other is the city where the Forró party will happen.
There will be at most 500 different cities. Input is terminated by EOF and there is a blank line beteween two input sets.
For each input set you should print the route for Chico to go from his city to the Forró party city, with a blank space between two cities, so he brakes only once and through the minimum number of cities. If there is more than one route, print that where the cities appear first in the input (see the last input). If there is no possible route print "No valid route.", without the quotes. Print a blank line between the outputs. See the examples below for the exact input/output format.
5 Natal Assu 50 Mossoro PaudosFerros 80 Assu Mossoro 40 Marcelino PaudosFerros 100 Assu PaudosFerros 65 Natal Mossoro 2 Limoeiro MoradaNova 140 Limoeiro Jaguaribe 130 Jaguaribe MoradaNova 4 Mossoro Paris 233 Mossoro NewYork 412 NewYork Tokio 501 Tokio Paris 420 Mossoro Tokio
Natal Assu PaudosFerros Mossoro Jaguaribe Limoeiro MoradaNova Mossoro Paris Tokio