#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 10000000;


vector<int> deikstra(int s, int n, vector<vector< pair<int, int> > > &g) {
	vector<int> d (n, INF);
	d[s] = 0;
	priority_queue < pair< int, int > > q;
	q.push (make_pair (0, s));
	while (!q.empty()) {
		int v = q.top().second, 
			cur_d = -q.top().first;
		q.pop();
		if (cur_d > d[v]) continue;
		for (int j = 0; j < g[v].size(); ++j) {
			int to = g[v][j].first,
				cost = g[v][j].second;
			if (d[v] + cost < d[to]) {
				d[to] = d[v] + cost;
				q.push(make_pair(-d[to], to));
			}
		}
	}
	//d[s] = INF;
	return d;
}




int main()
{
	freopen("SOCHI.IN", "r", stdin);
	int t;
	cin >> t;
	while (t--)
	{	
		int n ,m;
		cin >> n >> m;
		vector<vector< int > > matr(n);

		vector<vector< pair<int, int> > > g(n);
		for (int i = 0; i < m; i++) {
			int a,b,cost;
			cin >>a >>b>>cost;
			a--;
			b--;
			g[a].push_back(make_pair(b, cost));
			g[b].push_back(make_pair(a, cost));

			//cout << a << " " << b<< " " << cost <<endl;
		}



		int max = -1;
		for (int i =0 ; i <n; ++i) {
			matr[i] = deikstra(i, n, g);
			/*for (int j = 0; j<n ; ++j) {
				cout << matr[i][j] << " ";
			}
			cout <<endl;*/
		}
		for (int i =0 ; i <n; ++i) {
			for (int j =0 ; j <n; ++j) {
				if (i == j) continue;
				//cout << i << " " << j << ": " << matr[i][j] << " " <<matr[j][i] <<endl;
				matr[i][j] = min(matr[i][j], matr[j][i]);

				if (matr[i][j] > max && matr[i][j] != INF) 
					max = matr[i][j];
			}
		}
		cout << max <<endl;
		
	}

	return 0;
}
