#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
FILE*in=fopen("hamilton.in","r");
FILE*out=fopen("hamilton.out","w");
const int INF=1000000009;
int n,m,i,j,x,y,c,d[20][262144],mat[20][20],mask,po=1,masc,ras=INF;
struct str
{
    int nr,cost;
};
str a;
vector<str> v[20];
int main()
{
    fscanf(in,"%d%d",&n,&m);
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            mat[i][j]=INF;
        }
    }
    for(i=1;i<n;i++)
    {
        po*=2;
    }
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d%d",&x,&y,&c);
        a.nr=y;
        a.cost=c;
        v[x].push_back(a);
        mat[x][y]=c;
    }
    for(mask=0;mask<po;mask++)
    {
        for(i=0;i<n;i++)
        {
            d[i][mask]=INF;
        }
    }
    d[0][0]=0;
    for(mask=0;mask<po;mask++)
    {
        for(i=0;i<n;i++)
        {
            if(((mask*2+1)&(1<<i))!=0)
            {
                for(int t=0;t<v[i].size();t++)
                {
                    if(((mask*2+1)&(1<<(v[i][t].nr)))==0)
                    {
                        masc=mask|(1<<(v[i][t].nr-1));
                        d[v[i][t].nr][masc]=min(d[v[i][t].nr][masc],d[i][mask]+v[i][t].cost);
                    }
                }
            }
        }
    }
    for(i=0;i<n;i++)
    {
        ras=min(ras,d[i][po-1]+mat[i][0]);
    }
    if(ras>=INF)
    {
        fprintf(out,"Nu exista solutie");
        return 0;
    }
    fprintf(out,"%d",ras);
}