#include<iostream>
#include<string>
using namespace std;
#define MAX_S 1005
int road[MAX_S][MAX_S];
int cost[MAX_S];
int res,m,n;//所要的返回值，叉路口，道路
void Prim()
{
	int i,j,max,k;
	res=INT_MAX;
	for(i=1;i<=m;++i)
		cost[i]=road[1][i];
	for(i=1;i<m;++i)//找m-1条边
	{
		max=0;
		for(j=2;j<=m;++j)
		{
			if(cost[j]>max)
				max=cost[j],k=j;
		}
		cost[k]=-1;
		res=res<max?res:max;
		if(i==m-1) break;//结束时
		for(j=2;j<=m;++j)
		{
			if(cost[j]!=-1&&road[k][j]>cost[j])
				cost[j]=road[k][j];
		}
	}
}
int main()
{
	int t,i,j,k;
	cin>>t;
	for(k=1;k<=t;++k)
	{
		cin>>m>>n;
		memset(road,0,sizeof(road));
		for(i=1;i<=n;++i)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			road[b][a]+=c;
			road[a][b]+=c;
		}
	Prim();
	printf("Scenario #%d:\n%d\n\n",k,res);
	}
}