import java.util.*;
import java.io.*;

/**
 * Modified Dijkstra
 * Complexity: O(n^2) where n is the number of vertices
 * Author: Sebastian Kanthak
 */
public class heavy {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int scenarios = Integer.parseInt(in.readLine());
		for (int scen=1; scen <= scenarios; ++scen) {
			System.out.println("Scenario #"+scen+":");
			String[] tokens = in.readLine().split(" +");
			int n = Integer.parseInt(tokens[0]);
			assert 1 <= n && n <= 1000;
			int m = Integer.parseInt(tokens[1]);
			int[][] cost = new int[n][n];
			int[] weight = new int[n];
			boolean[] known = new boolean[n];
			int maxWeight = 1;
			while (m-- != 0) {
				tokens = in.readLine().split(" +");
				int u = Integer.parseInt(tokens[0])-1;
				int v = Integer.parseInt(tokens[1])-1;
				int w = Integer.parseInt(tokens[2]);
				assert 0 <= u && u < n;
				assert 0 <= v && v < n;
				assert 1 <= w && w <= 1000000;
				assert cost[u][v] == 0 && cost[v][u] == 0;
				cost[u][v] = cost[v][u] = w;
				maxWeight = Math.max(maxWeight,w);
			}
			weight[0] = maxWeight;
			for (int i=0; i < n; ++i) {
				int best = -1;
				int bestWeight = 0;
				for (int v=0; v < n; ++v) {
					if (!known[v] && weight[v] > bestWeight) {
						best = v;
						bestWeight = weight[v];
					}
				}
				known[best] = true;
				for (int v=0; v < n; ++v) {
					if (known[v]) continue;
					weight[v] = Math.max(weight[v],Math.min(weight[best],cost[best][v]));
				}
			}
			assert weight[n-1] > 0;
			System.out.println(weight[n-1]);
			System.out.println();
		}
	}
}
