#include <cstdio>
#include <vector>
using namespace std;
#define MAXN 18
#define INF 1000000000
vector <int> G[MAXN+1];
int dp[1<<MAXN][MAXN];
int cost[MAXN][MAXN];
int main(){
   FILE*fi,*fout;
   int n,m,a,b,x,i,j,min,k;
   fi=fopen("hamilton.in" ,"r");
   fout=fopen("hamilton.out" ,"w");
   fscanf(fi,"%d%d" ,&n,&m);
   for(i=0;i<n;i++)
     for(j=0;j<n;j++)
       cost[i][j]=INF;
   for(i=0;i<m;i++){
      fscanf(fi,"%d%d%d" ,&a,&b,&x);
      G[b].push_back(a);
      cost[a][b]=x;
   }
   for(i=0;i<n;i++)
     for(j=0;j<(1<<n);j++)
       dp[j][i]=INF;
   dp[1][0]=0;
   for(i=1;i<(1<<n);i++)
    for(j=0;j<n;j++)
     if(dp[i][j]==INF&&(i&(1<<j))>0)
       for(k=0;k<G[j].size();k++){
          x=G[j][k];
          if((i&(1<<x))>0&&x!=j&&dp[i][j]>dp[i-(1<<j)][x]+cost[x][j])
            dp[i][j]=dp[i-(1<<j)][x]+cost[x][j];
        }
   min=INF;
   for(j=1;j<n;j++)
     if(min>dp[(1<<n)-1][j]+cost[j][0])
      min=dp[(1<<n)-1][j]+cost[j][0];
   if(min==INF)
      fprintf(fout,"Nu exista solutie");
   else
      fprintf(fout,"%d" ,min);
   fclose(fi);
   fclose(fout);
   return 0;
}