#include <stdio.h>
int matrix[1001][1001], maxnum = 9999999, flag[1001], n;
int Dijstra(int a, int b)
{
	int i, j, mini, h, w;
	int d[1001];
	for(i = 0; i <= n; i++)
	{
		d[i] = 0;
		flag[i] = 0;
	}
	d[a] = maxnum;
	for(i = 0; i < n; i++)
	{
		mini = -1;
		for(j = 1; j <= n; j++)
		{
			if(flag[j] == 0 && d[j] > 0)
			{
				mini = d[j];
				h = j;
				break;
			}
		}
		if(mini == -1)break;
		else flag[h] = 1;
		for(j = 1; j <= n; j++)
		{
			if(flag[j] == 0 && matrix[h][j] != maxnum)
			{
				w = d[h] < matrix[h][j] ? d[h] : matrix[h][j];
				d[j] = d[j] > w ? d[j] : w;
			}
		}
	}
	return d[b];
}
int main()
{
	int T, m, num, i, j, u, v, dis;
	scanf("%d", &T);
	for(num = 1; num <= T; num++)
	{
		scanf("%d %d", &n, &m);
		for(i = 0; i <= n; i++)
		{
			for(j = 0; j <= n; j++)
				matrix[i][j] = maxnum;
		}
		for(i = 0; i < m; i++)
		{
			scanf("%d %d %d", &u, &v, &dis);
			matrix[u][v] = dis;
			matrix[v][u] = dis;
		}
		dis = Dijstra(1, n);
		printf("Scenario #%d:\n%d\n\n", num, dis);
	}
}