#include <iostream>
#include <vector>

using namespace std;

struct edge {
	int a, b, cost;
};


const int INF = 10000000;

int floyd(int n, vector<vector<int> > &matr)
{
	for (int i =0; i < n; ++i) {
		for (int j =0; j < n; ++j) {
			matr[i][j] = min(matr[i][j],matr[j][i]);


		}
	}
	for (int i =0; i < n; ++i) {
		for (int j =0; j < n; ++j) {
			for (int k =0; k < n; ++k) {
				if (matr[i][k] + matr[k][j] < matr[i][j])
					matr[i][j] = matr[i][k] + matr[k][j];
			}
		}
	}

	int max = -1;
	for (int i =0; i < n; ++i) {
		for (int j =0; j < n; ++j) {
			if (i ==j) 
				continue;
			if (max < matr[i][j] && matr[i][j] != INF)
				max = matr[i][j];
		}
	}
	return max;
}






int main()
{
	freopen("SOCHI.IN", "r", stdin);
	int t;
	cin >> t;
	while (t--)
	{	
		int n ,m;
		cin >> n >> m;
		m*=2;
		vector<vector<int> > matr(n);
		for (int i =0 ; i <n; ++i) {
			matr[i].resize(n, INF);
		}
		for (int i = 0; i < m; i+=2) {
			int a,b,cost;
			cin >>a >>b>>cost;
			a--;
			b--;
			matr[a][b] = cost;
		}
		cout << floyd(n, matr) << endl;
	}

	return 0;
}