#include<cstdio>
int n,m,i,j,k,c[18][18],C[1<<17][17],mask,cod,Cod,NS,ND,S[18],D[18],s,d,CI,sol,oo=1<<30;
int main()
{
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(;m;m--)
    {
        scanf("%d%d%d",&i,&j,&k);
        c[i][j]=k;
    }
    for(i=0,j=1;i<n-1;i++,j<<=1)mask|=j;
    for(i=0,j=1;i<n-1;i++,j<<=1)
    {
        if(c[n-1][i])C[mask-j][i]=c[n-1][i];
    }
    for(cod=mask;cod;cod--)
    {
        for(NS=0,ND=0,i=0,j=1;i<n-1;i++,j<<=1)
        {
            if(cod&j)D[++ND]=i;
            else
            {
                if(C[cod][i])S[++NS]=i;
            }
        }
        if(!NS)continue;
        for(i=1;i<=NS;i++)
        {
            s=S[i];
            CI=C[cod][S[i]];
            for(j=1;j<=ND;j++)
            {
                d=D[j];Cod=cod-(1<<d);
                if(!c[s][d])continue;
                if(!C[Cod][d]){C[Cod][d]=CI+c[s][d];continue;}
                if(C[Cod][d]>CI+c[s][d])C[Cod][d]=CI+c[s][d];
            }
        }
    }
    sol=oo;
    for(i=0;i<n-1;i++)
    {
        if(!C[0][i])continue;
        if(!c[i][n-1])continue;
        if(sol>C[0][i]+c[i][n-1])sol=C[0][i]+c[i][n-1];
    }
    sol==oo?printf("Nu exista solutie"):printf("%d",sol);
    return 0;
}