//#include <cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
#include <map>
#include<vector>
using namespace std;
int dp1[(1<<20)+1][22];
int dp2[(1<<20)+1][22];
int adj[22][22];
int ans=1000000000;
int a[100];
int tot;
int n;
void solve(int id)
{
    if (id==n-1)
    {
        int num=0;
        int x=0;
        for (int i=1;i<=n-2;i++)
            num+=a[i],x+=a[i]*(1<<(i-1));
        if (num==(n-2)/2)
        {
            int mn1=1000000000;
            int mn2=1000000000;
            for (int i=1;i<=n-2;i++)
            {
                for (int j=1;j<=n-2;j++)
                {
                    mn1=min(mn1,dp1[x][i]+dp2[tot-x][j]+adj[i][j]);
                    mn2=min(mn2,dp2[x][i]+dp1[tot-x][j]+adj[i][j]);
                }
            }
            ans=min(ans,mn1+mn2);
        }
    }
    else
    {
        a[id]=1;
        solve(id+1);
        a[id]=0;
        solve(id+1);
    }
}
int main()
{
    int c=1;
    while(cin>>n)
    {
        ans=1000000000;
        int m;
        cin>>m;
        for (int i=0;i<n;i++)
            for (int j=0;j<n;j++)
                adj[i][j]=1000000000;
        for (int i=0;i<m;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            adj[a][b]=adj[b][a]=c;
        }
        for (int k=0;k<n;k++)
            for (int j=0;j<n;j++)
                for (int i=0;i<n;i++)
                    adj[j][i]=min(adj[j][i],adj[j][k]+adj[k][i]);
        tot=(1<<(n-2))-1;
        for (int i=0;i<=n;i++)
            for (int j=0;j<=tot;j++)
                dp2[j][i]=dp1[j][i]=1000000000;
        dp1[0][0]=0;
        dp2[0][n-1]=0;
        for (int i=1;i<=tot;i++)
        {
            int h=i;
            for (int j=1;j<=n-2;j++)
            {
                int u=h%2;
                h/=2;
                if (u)
                {
                    for (int x=0;x<=n-2;x++)
                        dp1[i][j]=min(dp1[i][j],dp1[i-(1<<(j-1))][x]+adj[x][j]);
                    for (int x=1;x<=n-1;x++)
                        dp2[i][j]=min(dp2[i][j],dp2[i-(1<<(j-1))][x]+adj[x][j]);
                }
            }
        }
        solve(1);
        cout<<"Case "<<c++<<": ";
        cout<<ans<<endl;
    }
}