#include<iostream>
using namespace std;
int cross[1000001][3];
int n,m;
int place[1001];
int main()
{
	int cnt,x,i,max,a,b;
	cin>>cnt;
	for(x=1;x<=cnt;x++)
	{
		printf("Scenario #%d:\n",x);
		scanf("%d%d",&n,&m);
		for(i=0;i<m;i++) scanf("%d%d%d",&cross[i][0],&cross[i][1],&cross[i][2]);
		memset(place,0,sizeof(place));
		place[1]=0xfffffff;
		bool flag=true;
		while(flag)
		{
			flag=false;
			for(i=0;i<m;i++)
			{
				a=cross[i][0];b=cross[i][1];
				max=place[a]<cross[i][2]?place[a]:cross[i][2];
				if(max>place[b]) {place[b]=max;flag=true;}
				max=place[b]<cross[i][2]?place[b]:cross[i][2];
				if(max>place[a]) {place[a]=max;flag=true;}
			}
		}
		printf("%d\n\n",place[n]);
	}
	return 1;
}