// Arup Guha
// 6/6/2012
// Solution to 2012 World Finals Problem C: Bus Tour
import java.util.*;

public class c {

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);

		int loop = 1;
		while (stdin.hasNext()) {

			int n = stdin.nextInt();
			int m = stdin.nextInt();

			// Set up adjacency array. -1 means no connection.
			int[][] adj = new int[n][n];
			for (int i=0; i<n; i++) {
				Arrays.fill(adj[i], 1000000);
				adj[i][i] = 0;
			}
			for (int i=0; i<m; i++) {
				int v1 = stdin.nextInt();
				int v2 = stdin.nextInt();
				int dist = stdin.nextInt();
				adj[v1][v2] = dist;
				adj[v2][v1] = dist;
			}
			floyd(adj);

			// Ready to start coding here...
			int ans = solve(adj);
			System.out.println("Case "+loop+": "+ans);
			loop++;
		}
	}

	// Dictated by problem for shortest distances between any two places.
	public static void floyd(int[][] adj) {
		int n = adj.length;
		for (int k=0; k<n; k++) {
			for (int i=0; i<n; i++) {
				for (int j=0; j<n; j++) {
					if (adj[i][k] + adj[k][j] < adj[i][j])
						adj[i][j] = adj[i][k] + adj[k][j];
				}
			}
		}
	}

	// Usual combination.
	public static int choose(int n, int k) {

		int ans = 1;
		int num = n, den = 1;
		for (int i=1; i<=k; i++)
			ans = ans*num/den;
		return ans;
	}

	public static int solve(int[][] adj) {

		// ONLY ONE HOTEL, just go there and back =)
		if (adj.length == 3) {
			return 2*(adj[0][1] + adj[1][2]);
		}

		return getAns(adj);
	}

	// Items represents which hotels get visited first.
	public static int getAns(int[][] adj) {

		// two tables - all subsets from start, all subsets from end.
		int[][] start_first = getTSP(adj, 0);
		int[][] start_last = getTSP(adj, adj.length-1);

		int n = adj.length - 2;
		int limit;
		if (n%2 == 0)
		 	limit = start_first.length/2;
		else
		 	limit = start_first.length;

		int sizehalf = n/2;

		// Try to find the best path there.
		int best = 1000000;

		// Each row with the right number of items matches to a potential solution, so check that one out.
		for (int i=0; i<limit; i++) {

			if (countbits(i) == sizehalf) {

				// try to build path from here. Start -> these places -> others -> Last
				int other = start_first.length - 1 - i;
				int bestthere = 1000000;
				for (int j=0; j<start_first[i].length; j++) {
					for (int k=0; k<start_last[other].length; k++) {
						int curpath = start_first[i][j] + start_last[other][k] + adj[j+1][k+1];
						if (curpath < bestthere)
							bestthere = curpath;
					}
				}

				int bestback = 1000000;
				for (int j=0; j<start_last[i].length; j++) {
					for (int k=0; k<start_first[other].length; k++) {
						int curpath = start_last[i][j] + start_first[other][k] + adj[k+1][j+1];
						if (curpath < bestback)
							bestback = curpath;
					}
				}

				int cur = bestthere + bestback;

				if (cur < best)
					best = cur;
			}
		}

		return best;
	}

	// Gets the best TSP routes for each bitmask, starting from start.
	public static int[][] getTSP(int[][] adj, int start) {

		int n = adj.length-2;
		int maxbits = (n+1)/2;

		int[][] table = new int[1 << n][n];

		for (int i=0; i<table.length; i++)
			Arrays.fill(table[i], 1000000);

		// Off by one here - in adj the nodes are labeled 1-n, here they will be 0 to (n-1)
		for (int i=0; i<n; i++)
			table[1 << i][i] = adj[start][i+1];

		// Go through each row in the array.
		for (int i=0; i<table.length; i++) {

			int bits = countbits(i);

			if (bits > maxbits)
				continue;

			int saverow = i;
			int j = 0;
			while (saverow > 0) {

				// We can only build off this case if this bit is on.
				if ((saverow & 1) == 1) {

					int rest = i - (1 << j);

					int best = 1000000;
					for (int k=0; k<table[rest].length; k++) {

						if (table[rest][k] + adj[k+1][j+1] < best)
							best = table[rest][k] + adj[k+1][j+1];
					}

					// Don't overwrite my base cases.
					if (best < table[i][j])
						table[i][j] = best;

				}

				j++;
				saverow = saverow >> 1;
			}
		}

		return table;
	}

	// Returns the number of bits that are on in n.
	public static int countbits(int n) {

		int cnt = 0;
		while (n > 0) {
			if ((n & 1) == 1)
				cnt++;
			n = n >> 1;
		}
		return cnt;
	}
}