# include <iostream>
# include <vector>
# include <cstdio>
# include <algorithm>
# include <cmath>
# include <set>
using namespace std;
int n,k,u,v,c;
const int INF =10e7;
vector <vector<int> > d;
int main(){
	freopen("SOCHI.IN", "r", stdin);
	int T;
	cin>>T;
	while(T--){
		cin>>n>>k;
		d.clear();
		d.resize(n+1,vector <int> (n+1,INF));
		for(int i=0;i<k;i++)
		{
			cin>>u>>v>>c;
			if(c<d[u][v])
			d[u][v]=d[v][u]=c;
		}
		int max1=0;
		for(int k=1;k<=n;k++)
			for(int i=1;i<=n;i++)
				for(int j=1;j<=n;j++){
					//if(d[i][j]!=INF&& d[i][k]!=INF && d[k][j]!=INF)
						d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
				}


				for(int i=1;i<=n;i++)
					for(int j=1;j<=n;j++){
						{
							if( i!=j && d[i][j]!=INF) if(d[i][j]>max1) max1=d[i][j];
						}
					}
					cout<<max1<<endl;
	}
}
/*
2
7 7
1 2 2
1 5 1
1 4 2
1 3 6
2 3 3 
3 4 2
4 5 6
2 2 
1 2 5
2 1 10


*/