#include<iostream>
using namespace std;

const int Max=10000;


void work(int N,int k);
void DFS( int k,int n,int min);

int b[Max][Max]={0},mm;

int main()
{
	freopen("in.txt","r",stdin);
	int i,M,N,T,j,x,y,z,t(1),min(10000000);
	cin>>T;
	for( i=0; i<Max; i++)
		for( j=0; j<Max; j++)
			b[i][j]=0;
	while( T>0)
	{
		cin>>N>>M;
		for( i=0; i<M; i++)
		{
			cin>>x>>y>>z;
			b[x-1][y-1]=z;
		}
		DFS(0,N,min);

	
		
		cout<<"Scenario #"<<t<<":"<<endl;
		cout<<mm<<endl;
		mm=0;
		min=10000000;

		T--;t++;
		if(T>0)
			cout<<endl;
			for( i=0; i<N; i++)
			{
				
				for( j=0; j<N; j++)
					b[i][j]=0;
			}
	}
	return 0;
}


void DFS( int k,int n,int min)
{
	int i,j;
	if( k==n-1)
	{ 
		if(min>mm)
			mm=min;
		return;
	}

	for( i=k; i<n; i++)
	{
		for( j=0; j<n; j++)
			if(b[k][j]!=0)
			{
				if(min>b[k][j])
			
					min=b[k][j];
				DFS(j,n,min);
				
			}
	}
}