// Batuíra
#include <stdio.h>
#define REPOUSOS 105
#define COMPRIMENTO 20000

int matriz[REPOUSOS][REPOUSOS];

int main() {
	int repousos;
	int teste;
	int x, y, z;
	int i, j, k;

	for (teste=1; scanf("%d", &repousos)&&repousos!=0; teste++) {
		for (i=1; i<=repousos; i++) {
			for (j=1; j<=repousos; j++) {
				matriz[i][j]=COMPRIMENTO;
			}
		}	
		while (scanf("%d %d %d", &x, &y, &z)&&(x!=0||y!=0||z!=0)) {
			matriz[x][y]=z;
			matriz[y][x]=z;
		}
		for (i=1; i<=repousos; i++) {
			for (j=1; j<=repousos; j++) {
				for (k=1; k<=repousos; k++) {
					if (matriz[j][i]+matriz[i][k]<matriz[j][k]) {
						matriz[j][k]=matriz[j][i]+matriz[i][k];
					}
				}
			}
		}
		printf("Teste %d\n%d\n\n", teste, matriz[1][repousos]);
	}

	return 0;
}