#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const int maxn = 20;
const int oo = 1000000007;
int n,m,h;
int mat[maxn][maxn],dp[1<<maxn][maxn][maxn];

void enter()
{
	int u,v,t;
	for (int i=0; i<=n-1; i++)
		for (int j=0; j<=n-1; j++)
			if (i!=j)
				mat[i][j]=oo;
			else mat[i][j]=0;
	for (int i=0; i<=1<<n; i++)
		for (int j=0; j<=n-1; j++)
			for (int z=0; z<=n-1; z++)
				dp[i][j][z]=oo;
	for (int i=1; i<=m; i++)
	{
		cin >> u >> v >> t;
		mat[u][v]=min(mat[u][v],t);
		mat[v][u]=min(mat[v][u],t);
	}
	//cout << mat[3][4] << '\n';
}
void floyd()
{
	for (int x=0; x<=n-1; x++)
		for (int y=0; y<=n-1; y++)
			for (int z=0; z<=n-1; z++)
				mat[y][z]=min(mat[y][z],mat[y][x]+mat[x][z]);
}
int getbit(int x, int i)
{
	return (x >> i) & 1;
}
int countone(int x)
{
	int res=0;
	for (int i=0; i<=n-1; i++)
		if (getbit(x,i)==1) res++;
	return res;
}
// tra ve bit thu i cua so x
int clearbit(int x, int i)
{
	return x & (~(1 << i));
} 
int toggle(int x, int i)
{
	int number=x;
	number ^= 1 << i;
	return number;
}
int caldp(int mask, int u, int v)
{
	//cout << mask << ' ' << u << ' ' << v << '\n';
	if (dp[mask][u][v]==oo)
	{
		if (countone(mask)==0) dp[mask][u][v]=mat[u][v];
		else
		{
			for (int i=0; i<=n-1; i++)
				if (getbit(mask,i)==1)
					dp[mask][u][v]=min(dp[mask][u][v],caldp(clearbit(mask,i),u,i)+mat[i][v]);
		}
	}
	//cout << getbit(mask,n-2) << ' ';
	//for (int i=0; i<=n-1; i++)
	//	cout << getbit(mask,i);
	//cout << ' ' << getbit(mask,u) << ' ' << u << ' ' << v << ' ' << dp[mask][u][v] << '\n';
	return dp[mask][u][v];
}
int no(int x)
{
	int xx=x;
	for (int i=0; i<=n-1; i++)
		xx=toggle(xx,i);
	return xx;	
}
void printbit(int x)
{
	for (int i=0; i<=n-1; i++)
		cout << getbit(x,i);
	cout << ' ';
}
void solve(int t)
{
	int res=oo;
	h=n-2;
	//printbit(16);
	//printbit(no(16));
	//cout << '\n';
	for (int i=0; i<=1<<(n-1); i++)
		if ((countone(i)==h/2) and (getbit(i,0)!=1) and (getbit(i,n-1)!=1))
		{
			int res1=oo,res2=oo,res3=oo,res4=oo;
			for (int j=1; j<=n-2; j++)
				if (getbit(i,j)==1)
				{
					int mask=clearbit(i,j);
					int mas=clearbit(clearbit(clearbit(no(i),n-1),0),j);
					//cout << getbit(mas,j) << '\n';
					//printbit(mask);
					//printbit(mas);
					//cout << '\n';
					res1=min(res1,caldp(mask,0,j)+caldp(mas,n-1,j));
				}
			for (int j=1; j<=n-2; j++)
				if (getbit(i,j)==1)
				{
					int mask=clearbit(i,j);
					int mas=clearbit(clearbit(clearbit(no(i),n-1),0),j);
					//cout << getbit(mas,j)<< '\n';
					//printbit(mask);
					//printbit(mas);
					//cout << '\n';
					res2=min(res2,caldp(mask,n-1,j)+caldp(mas,0,j));
				}
			//cout << res1 << ' ' << res2 << '\n';
			res=min(res,res1+res2);				
		}
	if (n==3) res=(mat[0][1]+mat[1][2])*2;
	cout << "Case " << t << ": " << res << '\n';
}
int main()
{
	ios_base::sync_with_stdio(0);
	//freopen("1281.INP","r",stdin);
	//freopen("1281.OUT","w",stdout);
	int dem=0;
	while (cin >> n >> m)
	{
		dem++;
		enter();
		floyd();
		solve(dem);
		//cout << "OK\n";
	}
	return 0;
}