#include <stdio.h>

using namespace std;

const int N = 20;
const int M = 400;
const int P = 1 << 19;
const int MAX = 20000000;

int cost[N][N];
int d[P][N];

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

    int n,m,i,j,k,x,y,c,minim;
    fscanf(in,"%d%d",&n,&m);

    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            cost[i][j]=MAX;

    for(i=0;i<m;i++)
    {
        fscanf(in,"%d%d%d",&x,&y,&c);
        cost[x][y]=c;
    }

    for(i=1;i<(1<<n);i+=2)
        for(j=0;j<n;j++)
            d[i][j]=MAX;

    d[1][0]=0;
    for(i=1;i<(1<<n);i+=2)
    {
        for(j=1;j<n;j++)
        {
            if(i&(1<<j))
            {
                minim=MAX;
                for(k=0;k<n;k++)
                    if((i&(1<<k)) && k!=j)
                        if(minim > cost[k][j]+d[i^(1<<j)][k])
                            minim = cost[k][j]+d[i^(1<<j)][k];
                d[i][j]=minim;
            }
            //fprintf(out,"%d ",d[i][j]);
        }
        //fprintf(out,"\n");
    }
    minim=MAX;
    for(i=1;i<n;i++)
        if(minim > cost[i][0]+d[(1<<n)-1][i])
            minim = cost[i][0]+d[(1<<n)-1][i];
    if(minim==MAX)
        fprintf(out,"Nu exista solutie");
    else
        fprintf(out,"%d",minim);
    return 0;
}