#include <cstdio>

FILE* in=fopen("hamilton.in","r");
FILE* out=fopen("hamilton.out","w");

int nrnod,nrmuc;

int m[20][20];
int d[1<<18][20];

int INF=2000000002;


int min(const int &a,const int &b)
{
    if(a<b)
        return a;
    else
        return b;
}

void modeleaza(int x)
{
    for(int j=1; j<nrnod; j++)
    {
        for(int k=1; k<nrnod; k++)
        {
            if(m[k][j]!=0)
                d[x][j]=min(d[x][j],d[x^(1<<j)][k]+m[k][j]);
        }
    }
}

int main()
{
    fscanf(in,"%d %d",&nrnod,&nrmuc);

    int a,b,c;

    for(int i=1; i<=nrmuc; i++)
    {
        fscanf(in,"%d%d%d",&a,&b,&c);
        m[a][b]=c;
    }

    for(int i=0; i<nrnod; i++)
    for(int j=0; j<1<<18; j++)
        d[j][i]=INF;

    for(int i=1; i<nrnod; i++)
    {
        d[ 1<<i ][i]=0;
    }


    for(int i=1 ; i< 1<<(nrnod-1); i++)
    {
        modeleaza(i);
    }

    int minim=INF;

    for(int i=1; i<nrnod; i++)
    {
        if(m[i][0]!=0)
            minim=min(minim,d[(1<<18)-1][i]+m[i][0]);
    }

    if(minim==INF)
        fprintf(out,"Nu exista solutie");
    else
        fprintf(out,"%d",minim);


    return 0;
}