#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
int n, m, d[1010], oo = 1000000000;
bool isNew[1010];

vector<vector<pair<int, int> > > a;
priority_queue<pair<int, int> > que;

void dejkstra(int v)
{
	int i, j, u, c;

	for(i = 0; i < n; i++)
		d[i] = oo;

	que.push(make_pair(0, v));
	while(!que.empty())
	{
		c = -que.top().first;
		v = que.top().second;

		que.pop();

		if(c < d[v])
		{
			d[v] = c;

			for(j = 0; j < a[v].size(); j++)
			{
				u = a[v][j].first;
				c = a[v][j].second;

				if(d[v] + c < d[u])
					que.push(make_pair(-(d[v] + c), u));
			}
		}
	}
}

int main()
{

	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);

	int tests, i, j, v, u, c;
	scanf("%d", &tests);
	while(tests > 0)
	{
		int  res = -1;

		scanf("%d%d", &n, &m);

		a.resize(n);

		for(i = 0; i < m; i++) {
			scanf("%d%d%d", &v, &u, &c);
			v--;
			u--;
			a[v].push_back(make_pair(u, c));
			a[u].push_back(make_pair(v, c));
		}

		for(i = 0; i < n; i++)
			isNew[i] = true;

		for(i = 0; i < n; i++)
		{
			if(!isNew[i])
				continue;

			dejkstra(i);

			int lmax = -1;

			for(j = 0; j < n; j++)
			{
				if(d[j] < oo)
				{
					res = max(res, (i != j) ? d[j]: -1);
					lmax = max(lmax, d[j]);
				}
			}

			for(j = i + 1; j < n; j++)
			{
				if(lmax + d[j] <= res) {
					isNew[j] = false;
				}
			}

		}

		a.clear();
		
		printf("%d\n", res);
		tests--;
	}

	return 0;
}