travelling salesman

#include<bits/stdc++.h>
using namespace std;

int bitOn(int N,int pos){return N=N | (1<<pos);}
bool bitCheck(int N,int pos){return (bool)(N & (1<<pos));}

int n,m,dp[(1<<16)+5],dist[20][20],d[20];

int giveres(int mask)
{
    if(__builtin_popcount(mask)==n)return 0;
    if(dp[mask]!=-1)return dp[mask];
    int ans=INT_MAX/10;
    for(int i=0;i<n;i++)
    {
        if(!bitCheck(mask,i))
        {
            int temp=bitOn(mask,i);
            for(int j=0;j<n;j++)
            {
                if(!bitCheck(temp,j))
                {
                    ans=min(ans,giveres(bitOn(temp,j))+dist[i][j]);
                }
            }
        }

    }

    return dp[mask]=ans;
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int q=0;q<t;q++)
    {
       memset(d,0,sizeof(d));int ans=0;
        scanf("%d%d",&n,&m);
        for(int i=0;i<=15;i++)
        {
            for(int j=0;j<=15;j++)
            {
                if(i!=j)dist[i][j]=INT_MAX/10;
                else dist[i][j]=0;
            }
        }
        for(int i=0;i<m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            a--;b--;
            d[a]++;
            d[b]++;
            dist[a][b]=min(dist[a][b],c);
            dist[b][a]=dist[a][b];
            ans+=c;
        }

        for(int k=0;k<n;k++)
        {
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<n;j++)
                {
                    if(dist[i][k]+dist[k][j]<dist[i][j])
                    {
                        dist[i][j]=dist[i][k]+dist[k][j];
                    }
                }
            }
        }
        int mask=0;
        memset(dp,-1,sizeof(dp));
        for(int i=0;i<n;i++)
        {
            if(d[i]%2==0)
                mask=bitOn(mask,i);
        }

        int x=giveres(mask)+ans;
        printf("Case %d: %d\n",q+1,x);


    }

    return 0;
}