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

int cost[20][20],M[(1<<20)][20],res[(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;
          res[j][i]=infinit;
         }
   M[1][0]=res[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]);
                    
                    
   
   /* 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))
                        res[j][k] = min(res[j][k], res[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;
}