#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int map[1010][1010];
int clost[1010];
bool is[1010];
int main()
{
	int n, m,s,e,w,t;
	cin >> t;
	while (t) 
	{
		cin >> n >> m;
		memset(map, 0, sizeof(map));
		memset(is, 0, sizeof(is));
		for (int i = 0; i < m; ++i)
		{
			cin >> s >> e >> w;
			map[s][e] = w;
			map[e][s] = w;
		}
		for (int i = 1; i <= n; ++i)
			clost[i] = map[1][i];
		for (int i = 1; i <= n; ++i)
		{
			int max = -1,bj=0;
			for(int j=1;j<=n;++j)
				if (!is[j] && max < clost[j])
				{
					max = clost[j];
					bj = j;
				}
			is[bj] = 1;
			for (int j = 1; j <= n; ++j)
				if ((min(map[bj][j],clost[bj])>clost[j])&&(!is[j]))
					clost[j] = min(map[bj][j] , clost[bj]);
		}
		printf("Scenario #%d:\n", t);
		printf("%d\n\n", clost[n]);
		t--;
	}
	return 0;
}