#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <conio.h>
#include <vector>
#include <set>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <assert.h>

using namespace std;

#define INF 1000000000
 

int main()
{
	freopen("sochi.in", "r", stdin);
	//freopen("sochi.out", "w", stdout);

	int test;

	cin >> test;

	for(int t=0; t<test; t++)
	{
		int n, m;
		cin >> n >> m;
		
		assert(n >=1 && n<= 1000);
		assert(m >=0 && m <= 3000);
		
		vector< vector<pair<int, int>>> roads(n);

		for(int i=0; i<m; i++)
		{
			int start, end, len;
			cin >> start >> end >> len;
			
			assert(start >= 1 && start <= n);
			assert(end >= 1 && end <= n);
			assert(len >= 1 && len <= 100000);
	
			if (start == end) continue;
			
			roads[start-1].push_back(make_pair(end-1, len));
			roads[end-1].push_back(make_pair(start-1, len));
		}
	
		int maxlen = -1;

		for(int cur = 0; cur < n; cur++)
		{
			vector<int> distance(n, INF);
			distance[cur] = 0;
			set<pair<int, int>> q;
			q.insert(make_pair(distance[cur], cur));

			while(!q.empty())
			{
				int start = q.begin()->second;
				q.erase(q.begin());

				for(vector<pair<int, int>>::iterator i = roads[start].begin(); i != roads[start].end(); i++)
				{
					int end = i ->first;
					int len = i->second;
					if (distance[start] + len < distance[end])
					{
						q.erase(make_pair(distance[end], end));
						
						distance[end] = distance[start] + len;

						q.insert(make_pair(distance[end], end));
					}
				}
			}
			
			for(int i=0; i<n; i++)
			{
				if (distance[i] == INF || i == cur) distance[i] = -1;
				
				maxlen = max(maxlen, distance[i]);				
			}			
		}		
		cout << maxlen << endl;
	}	

	return 0;
}