import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {

	/**
	 * @param args
	 * @throws Exception
	 */
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new FileReader("SOCHI.in"));
		int t = Integer.parseInt(in.readLine());
		for (int k = 0; k < t; k++) {
			StringTokenizer st = new StringTokenizer(in.readLine());
			int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st
					.nextToken());
			int ves[][] = new int[n + 1][n + 1];
			for (int i = 0; i < m; i++) {
				st = new StringTokenizer(in.readLine());
				int l = Integer.parseInt(st.nextToken()), j = Integer
						.parseInt(st.nextToken()), v = Integer.parseInt(st
						.nextToken());
				if (ves[l][j] == 0) {
					ves[l][j] = v;
					ves[j][l] = v;
				} else {
					if (ves[i][j] > v) {
						ves[l][j] = v;
						ves[j][l] = v;
					}
				}
			}
			int max = -1;
			int min[] = new int[n + 1];
			for (int c = 0; c < n+1; c++) {

				ArrayList pretend = new ArrayList();
				ArrayList isp = new ArrayList();

				pretend.add(new Integer(c));
				for (int i = 0; i < n + 1; i++) {

					min[i] = Integer.MAX_VALUE;

				}
				min[c] = 0;
				while (!pretend.isEmpty()) {
					ArrayList prom = new ArrayList();
					Object lk = getMin(pretend);
					int l = Integer.parseInt(lk.toString());
					for (int j = 1; j < min.length; j++) {

						if (ves[l][j] > 0)
							if (min[j] > min[l] + ves[l][j]) {
								min[j] = min[l] + ves[l][j];
								pretend.add(new Integer(j));
							}

					}

					pretend.remove(lk);
				}
				
				for (int i = 1; i < n + 1; i++) {
					if (min[i] < Integer.MAX_VALUE)
						if (max < min[i]) {
							max = min[i];
						}

				}

				
			}
			System.out.println(max);
		}

	}

	private static Object getMin(ArrayList pretend) {
		int mi = Integer.MAX_VALUE;
		for (int i = 0; i < pretend.size(); i++) {
			if (mi > Integer.parseInt(pretend.get(i).toString())) {
				mi = Integer.parseInt(pretend.get(i).toString());
			}
		}
		return new Integer(mi);
	}

}
