Batuíra

As batuíras são aves migrantes de pequeno porte que fazem seus ninhos no hemisfério norte, na tundra ártica (no Canadá e Groenlândia). Elas permanecem naquela região durante o verão (de maio a junho no hemisfério norte), que é muito curto, e depois migram para o outro lado da Terra. As batuíras-de-peito-vermelho fazem seus ninhos em um raio de até mil quilômetros do Pólo Norte. Quando chega a época de migrarem, fazem longos vôos, em bandos, até o Sudeste dos Estados Unidos. Em seguida, partem para a Patagônia, onde passam o período quente do Hemisfério Sul (de outubro a março). Em março começam sua longa viagem de volta.

Como essas aves se orientam para realizar trajetos tão longos? Não existe uma resposta definitiva, mas apenas hipóteses. Uma das mais prováveis que é elas têm a capacidade de realizar a navegação celestial, isto é, de se guiarem pelos astros. Outra hipótese é que poderiam sentir os campos magnéticos da Terra, utilizando-os como referência.

As batuíras fazem longos vôos, mas precisam parar de vez em quando para recuperar suas forças, em pontos de repouso, normalmente praias ou beiras de lagos. Dependendo do trajeto escolhido e da localização dos pontos de repouso, a viagem migratória das batuíras pode variar em cerca de 10% de ano a ano -- o que, no caso, significa uma variação de mil quilômetros!

Tarefa

Você deve escrever um programa que, dadas as distâncias entre possíveis pontos de repouso das batuíras determine o comprimento total do menor trajeto que as aves poderiam seguir em sua viagem do hemisfério norte para o hemisfério sul.

Entrada

A entrada é composta de vários conjuntos de teste. A primeira linha de um conjunto de teste contém um número inteiro N que indica a quantidade de pontos de repouso . Os pontos de repouso são numerados de 1 a N, sendo 1 o ponto de partida e N o ponto de chegada do vôo migratório. As linhas seguintes contêm, cada uma, três inteiros não negativos X e Y que indicam que a distância do ponto de repouso X ao ponto de repouso Y é Z. O final do conjunto de teste é indicado por X = 0,Y = 0 e Z = 0. O final da entrada é indicado por N = 0.

Exemplo de Entrada

3
1 2 300
2 3 400
0 0 0
6
1 2 10
1 3 20
5 2 4
3 4 7
6 5 30
2 6 50
4 5 7
4 6 9
0 0 0
0

Saída

Para cada conjunto de teste da entrada seu programa deve produzir três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato "Teste n", onde n é numerado a partir de 1. A segunda linha deve conter o comprimento do menor trajeto conforme determinado pelo seu programa. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo de Saída

Teste 1
700

Teste 2 
30

(esta saída corresponde ao exemplo de entrada acima)

Restrições

0 ≤ N ≤ 100 (N = 0 apenas para indicar o final da entrada)
0 ≤ X ≤ N (X = 0 apenas para indicar o final do conjunto de teste)
0 ≤ Y ≤ N (Y = 0 apenas para indicar o final do conjunto de teste)
0 ≤ Z ≤ 1000 (Z = 0 apenas para indicar o final do conjunto de teste)