#include <cstdio>

using namespace std;
const int M=310;
const int N=20;
const int put=262144;
const int inf=99999999;
int d[262150][20];
int cost[20][20];
int p;
int main()
{
    FILE *in,*out;
    in=fopen("hamilton.in","r");
    out=fopen("hamilton.out","w");
    int n,m,x,y,c,i,j,k,min,ras;
    fscanf(in,"%d%d",&n,&m);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            cost[i][j]=inf;
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d%d",&x,&y,&c);
        cost[x][y]=c;
    }
    for(i=0;i<=put;i++)
        for(j=0;j<=n;j++)
            d[i][j]=inf;
    d[1][0]=0;
    for(i=1;i<(1<<n);i=i+2)
        for(j=1;j<n;j++)
        {
            if(i&(1<<j)!=0)
            {
                min=inf;
                for(k=0;k<n;k++)
                {
                    if( (i&(1<<k)!=0) && (k!=j) )
                    {
                        if(min> cost[k][j]+d[i^(1<<j)][k])
                            min= cost[k][j] + d[i^(1<<j)][k];
                    }
                }
                d[i][j]=min;
            }
        }
    /*for(i=1;i<(1<<n);i=i+2)
    {
        for(j=1;j<n;j++)
        {
            fprintf(out,"%d ",d[i][j]);
        }
        fprintf(out,"\n");
    }
    /*/
    ras=inf;
    for(j=1;j<n;j++)
    {
        if(ras>d[(1<<n)-1][j]+cost[j][0])
            ras=d[(1<<n)-1][j]+cost[j][0];
    }
    if(ras!=inf)
        fprintf(out,"%d",ras);
    else
        fprintf(out,"Nu exista solutie");
    return 0;
}