10793

#include <iostream>
#include <map>
#include <vector>

#define INF 1000000000

using namespace std;

int L,D;
int gr[105][105];
map<int,int> mp;

int main()
{
	int kase=1;
	int t,u,v,c;
	cin>>t;

	while(t--)
	{
		for(int i=0;i<105;i++)
		{
			for(int j=0;j<105;j++)
			{
				if(i==j)
				gr[i][j]=0;
				else
				gr[i][j]=INF;
			}

		}
		cin>>L>>D;
		for(int i=1;i<=D;i++)
		{
			cin>>u>>v>>c;
			if(gr[u][v]>c)
			{
				gr[u][v]=c;
				gr[v][u]=c;
			}
		}


		for(int k=1;k<=L;k++)
		{
			for(int i=1;i<=L;i++)
			{
				for(int j=1;j<=L;j++)
				{
					if(gr[i][j]>gr[i][k]+gr[k][j])
			  			gr[i][j]  =  gr[i][k]+gr[k][j];

				}
			}
		}

		mp.clear();
		for(int i=1;i<=L;i++)
		{
			if(gr[1][i]!=INF && gr[1][i]==gr[2][i] && gr[1][i]==gr[3][i] && gr[1][i]==gr[4][i] && gr[1][i]==gr[5][i])
			{
				mp[i]=gr[1][i];
			}
		}
		/*cout<<"sz "<<mp.size()<<"\n";
		for(map<int,int>::iterator ii = mp.begin();ii!=mp.end();++ii)
			cout<<ii->first<<" "<<ii->second<<"\n";
			*/
		if(mp.size()==0)
		{
			cout<<"Map "<<kase++<<": ";
			cout<<"-1\n";
		}
		else
		{
			//int MN = INF;
			int mx =-1;
			int Mmx =INF;
			for(map<int,int>::iterator ii = mp.begin();ii!=mp.end();++ii)
			{
				int val =ii->first;
				mx =-1;
				for(int j=1;j<=L;j++)
				{
					if(gr[j][val]>mx)
					mx = gr[j][val];
				}
				//cout<<"m "<<mx<<"\n";
				if(Mmx>mx)
				Mmx = mx;
			}
			cout<<"Map "<<kase++<<": ";
			if(Mmx==INF)
			cout<<-1<<"\n";
			else
			cout<<Mmx<<"\n";
		}

	}

	return 0;
}