SPOJ Brasil

Chico adora dirigir, sempre em alta velocidade. Outra grande paixăo de Chico é o Forró, um tipo de música muito popular no nordeste do Brasil. Mas infelizmente năo acontecem muitas festas de Forró na cidade de Chico e ele precisa viajar para outras cidades se ele quiser ir para uma festa de Forró.

Chico, além de dirigir e dançar Forró, também gosta de computadores e de programaçăo. Como ele é um programador muito bom, ele decidiu fazer um programa para calcular a melhor maneira para ir da cidade dele para uma cidade onde irá acontecer uma festa de Forró. Porém, Chico precisa sair com sua namorada agora e năo pode fazer o programa, entăo ele pediu a sua ajuda.

O carro de Chico, contudo, está com um problema nos freios e Chico năo pode consertá-los, pois vai ficar sem dinheiro para comprar o ingresso da festa e tomar algumas cervejas. Desse modo, vocę deve achar uma rota onde Chico freie somente uma vez, quando ele chegar na cidade de destino. Dado que ele năo pode frear, é perigoso passar por uma cidade, entăo Chico deve atravessar o menor número de cidades possível durante a viagem.

Entrada

A entrada contém vários conjuntos de teste. A descriçăo de cada conjunto é dada a seguir:

Cada conjunto começa com um inteiro R (0 < R ≤ 5000), o número de estradas. As próximas R linhas descrevem as estradas onde a descriçăo de uma estrada consiste do nome de duas cidades, sendo que o nome de cada cidade tem no máximo 30 caracteres, e V (0 < V ≤ 1000) a velocidade do carro de Chico quando ele viaja entre as cidades A e B. Vocę pode assumir que A e B năo săo a mesma cidade e que pode existir mais de uma estrada entre duas cidades. Após essas R linhas, há uma linha com o nome de duas cidades, a primeira delas é a cidade onde Chico mora e a segunda é a cidade onde a festa de Forró irá acontecer.

Há no máximo 500 cidades diferentes. A entrada é terminada por EOF e há uma linha em branco entre dois conjuntos de teste.

Saída

Para cada conjunto de teste vocę deve imprimir a rota para Chico ir da cidade dele para a cidade da festa de Forró, de modo que ele freie somente uma vez e atravesse o menor número de cidades possível. Se há mais de uma rota, imprima aquela que aparece primeiro na entrada (veja o último exemplo de entrada). Se năo há rota possível, imprima "No valid route.", sem as aspas. Imprima uma linha em branco entre cada saída. Veja os exemplos a seguir para o formato exato de entrada/saída.

Exemplo

 
Entrada:
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

Saída:
Natal Assu PaudosFerros Mossoro

Jaguaribe Limoeiro MoradaNova

Mossoro Paris Tokio

Autor do Problema: Sérgio Queiroz de Medeiros