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

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

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,x,y,k,v,infinit=(1<<27);
   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,&cost[x][y]);
   
   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]);
   fclose(f);
   f=fopen("hamilton.out","w");

   
   
   fprintf(f,"%d",x);
   fclose(f);
   //getch();               
   return 0;
}