# include <iostream>
# include <vector>
# include <cstdio>
# include <algorithm>
# include <cmath>
# include <set>
#include <queue>
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--){
		scanf("%d%d",&n,&k);
		d.clear();
		d.resize(n+1,vector <int> (n+1,INF));
		for(int i=0;i<k;i++)
		{
			scanf("%d%d%d",&u,&v,&c);
			if(c<d[u][v])
				d[u][v]=c;
		}
		vector <vector<pair<int,int> > > g(n+1); 
		for(int i=1;i<=n;i++)
			for(int j=i+1;j<=n;j++){
				if(d[i][j]!=INF){ g[i].push_back(make_pair(j,d[i][j]));g[j].push_back(make_pair(i,d[i][j])); }}
				vector <int> d(n+1,INF);
				priority_queue <pair<int,int> > q;
				d[1]=0;
				q.push(make_pair(1,0));
				while(!q.empty())
				{	
					int v=q.top().first;
					int dist=-q.top().second;
					q.pop();
					if(d[v]<dist) continue;
					for(int i=0;i<g[v].size();i++)
					{
						int to=g[v][i].first;
						int len=g[v][i].second;
						if(d[to]>d[v]+len)
						{
							d[to]=d[v]+len;
							q.push(make_pair(to,-d[to]));
						}
					}
				}

				int max1=0,t=1;
				for(int i=1;i<=n;i++)
					if(d[i]!=INF && d[i]>max1) {max1=d[i];t=i;}

					d.assign(n+1,INF);
					priority_queue <pair<int,int> > q1;
					d[t]=0;
					q1.push(make_pair(t,0));
					while(!q1.empty())
					{	
						int v=q1.top().first;
						int dist=-q1.top().second;
						q1.pop();
						if(d[v]<dist) continue;
						for(int i=0;i<g[v].size();i++)
						{
							int to=g[v][i].first;
							int len=g[v][i].second;
							if(d[to]>d[v]+len)
							{
								d[to]=d[v]+len;
								q1.push(make_pair(to,-d[to]));
							}
						}
					}
max1=0;
					for(int i=1;i<=n;i++)
						if(d[i]!=INF && d[i]>max1) {max1=d[i];} 
						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


*/