#include<stdio.h>
#include<stdlib.h>
//#include<limits.h>

int cost[19][19],M[(1<<19)][19];

int min(int a,int b)
   {
    if(a<b) return a;
    return b;
   }
int main()
{
   FILE *f;
   f=fopen("hamilton.in","r");
   int i,j,n,m,c,x,y,k,v,infinit=(1<<30);
   fscanf(f,"%d%d",&n,&m);
   
   for(i=0;i<n;i++)
      for(j=0;j<n;j++)
         cost[i][j]=infinit;
   
   for(i=0;i<m;i++)
      {
       fscanf(f,"%d%d%d",&x,&y,&c);
       cost[x][y]=c;
      }
   for(i=0;i<n;i++)
      for(j=0;j<(1<<n);j++)
          M[j][i]=infinit;
   M[1][0]=0;
         
   for(j=0;j<(1<<n);j++)
      for(k=0;k<n;k++)
         if(j&(1<<k))
           for(v=0;v<n;v++)
              if(j&(1<<v))
                if(cost[v][k]!=infinit)
                  if(v!=k)
                    M[j][k]=min(M[j][k],M[j^(1<<k)][v]+cost[v][k]);
   
   x=infinit;
   for(i=0;i<n;i++)
      if(M[(1<<n)-1][i]!=infinit) 
        x=min(x,M[(1<<n)-1][i]+cost[i][0]);
      
   fclose(f);
   f=fopen("hamilton.out","w");
   fprintf(f,"%d",x);
   fclose(f);             
   return 0;
}