# include <fstream>
# include <iostream>
# include <string>
# include <vector>
# include <queue>
# include <climits>
using namespace std;

const int MAXN=1002;
const int MAXINT=100006;

struct edgenode{
	int b,w;
	edgenode *next;
};
struct graph{
	int n;
	edgenode *e[MAXN];
};
void add_edge(graph *g,int a,int b,int w){
	edgenode *p=new edgenode;
	p->b=b;
	p->w=w;
	p->next=g->e[a];
	g->e[a]=p;
	edgenode *q=new edgenode;
	q->b=a;
	q->w=w;
	q->next=g->e[b];
	g->e[b]=q;
}
int dijkstra(graph *g,int start){
	int i,n=g->n;
	vector<int> d (n,INT_MAX);
	vector<char> used (n,false);
	vector<int> parent (n,-1);
	d[start]=0;
	queue<int> q;
	q.push(start);
	while(!q.empty()){
		int v=q.front();
		q.pop();
		used[v]=true;
		edgenode *p=g->e[v];
		while(p!=NULL){
			int to=p->b;
			int cap=p->w;
			if(d[to]>d[v]+cap){
				d[to]=d[v]+cap;
				parent[to]=v;
			}
			p=p->next;
		}
		int dist=INT_MAX;
		v=-1;
		for(i=0;i<n;i++){
			if(d[i]<dist && !used[i]){
				dist=d[i];
				v=i;
			}
		}
		if(v!=-1) 
			q.push(v);
	}
	int Max=0,iMax=0;
	for(i=0;i<n;i++)
		if(d[i]>Max && d[i]!=INT_MAX){
			iMax=i;
			Max=d[i];
		}
	return Max;
}
void main ()
{
	ifstream in("SOCHI.IN");
	in.sync_with_stdio(false);
	int I,T;
    in>>T;
	for(I=0; I<T; I++)
	{	
		int i,j,k,N,M;
		graph *g=new graph;
		in>>N>>M;
		g->n=N;
		for(i=0;i<N;i++)
			g->e[i]=NULL;
		for(i=0;i<M;i++){
			int a,b,c;
			in>>a>>b>>c;
			add_edge(g,a-1,b-1,c);
		}
		int MAx=0;
		for(i=0;i<N;i++){
			int t=dijkstra(g,i);
			if(MAx<t)
				MAx=t;
		}
		cout<<MAx<<endl;
	}
	//system("pause");
}
