Intermediário Informática - Semana 21

Caminho mais largo

Será dado um grafo ponderado e duas cidades, pede-se o caminho com a maior aresta mínima entre essas duas cidades.

Entrada

A entrada irá conter um ou mais casos de teste. A primeira linha de cada caso de teste conterá dois inteiros: o número de vértices n (  2 \leq n \leq 200 ) e o número de arestas r ( 1 \leq r \leq 19900 ) que compõem o grafo.

Em seguida, R linhas seguirão, cada um descrevendo uma aresta, nomeando os dois vértices ligados por esta e dando o peso da aresta. Os nomes dos vértices não terão mais de 30 caracteres e não contêm espaço em branco. Os pesos são inteiros no intervalo de 0 - 10000. As arestas são bidirecionais.

A última linha do caso de teste contém dois nomes de vértices: início e destino.

Entrada será terminada por dois valores de 0 para n e r.

Saída

Para cada caso de teste, imprima três linhas:
Uma linha dizendo "Scenario #x ", onde x é o número do caso de teste.
Uma linha dizendo "y ", onde y é a menor aresta do caminho encontrado.
Uma linha em branco.

Exemplo de Entrada Exemplo de Saída
4 3
Fortaleza Eusebio 100
Eusebio Juazeiro 80
Juazeiro Mumbaba 120
Fortaleza Mumbaba
5 5
Karl Stut 100
Stut Ulm 80
Ulm Muen 120
Karl Ham 220
Ham Muen 170
Muen Karl
0 0
Scenario #1
80

Scenario #2
170