#include<cstdio>
#include<vector>
#include<algorithm>

const int INF=2047483647;

const int NMAX=18;

std::vector < std::pair<int,int> > v[NMAX];

int d[NMAX+1][(1<<NMAX)];

int main()
{
 FILE *fin=fopen("hamilton.in","r");
 int n,m;
 fscanf(fin,"%d %d ",&n,&m);
 for(int i=1;i<=m;i++)
    {
     int x,y,c;
     fscanf(fin,"%d %d %d ",&x,&y,&c);
     v[y].push_back(std::make_pair(x,c));
    }
 fclose(fin);
 for(int i=0;i<=n;i++)
     for(int j=0;j<(1<<n);j++)
         d[i][j]=INF;
 d[0][1]=0;
 int pp;
 for(int mask=0;mask<(1<<n);mask++)
    {
     for(int i=0;i<n;i++)
        {
         if(mask&(1<<i))
            {
             for(int j=0;j<v[i].size();j++)
                {
                 int k=v[i][j].first;
                 if(mask&(1<<k))
                    {
                     d[i][mask]=std::min(d[i][mask],d[k][mask-(1<<i)]+v[i][j].second);
                     //d[i][mask]=min(d[i][mask],d[j][mask-(1<<i)]+a[i][j]);
                    }
                }
            }
        }
    }
 int rez;
 rez=INF;
 for(int i=0;i<n;i++)
     rez=std::min(rez,d[i][(1<<n)-1]+v[i][0].second);
 FILE *fout=fopen("hamilton.out","w");
 fprintf(fout,"%d\n",rez);
 fclose(fout);
 return 0;
}