#include <stdio.h>
#define INF 1000000000
#define MAXN 18
#define MAXM 307
int v[MAXN],l[MAXM],next[MAXM],c[MAXN][MAXN],d[1<<MAXN][MAXN];
int main(){
    FILE *fin=fopen("hamilton.in","r");
    FILE *fout=fopen("hamilton.out","w");
    int n,m,i,j,x,y,k=1;

    fscanf(fin,"%d%d",&n,&m);
    for(i=0; i<n; i++)
      for(j=0; j<n; j++)
        c[i][j]=INF;
    for(i=0; i<(1<<n); i++)
      for(j=0; j<n; j++)
        d[i][j]=INF;
    for(i=0; i<m; i++){
      fscanf(fin,"%d%d",&x,&y);
      fscanf(fin,"%d",&c[x][y]);
      l[k]=x;
      next[k]=v[y];
      v[y]=k++;
    }
    d[1][0]=0;
    for(i=3; i<(1<<n); i++)
      for(j=1; j<n; j++)
        if(i&(1<<j)){
          x=v[j];
          while(x){
            if(i&(1<<l[x]) && d[i][j]>d[i^(1<<j)][l[x]]+c[l[x]][j])
              d[i][j]=d[i^(1<<j)][l[x]]+c[l[x]][j];
            x=next[x];
          }
        }
    int min=INF;
    for(i=1; i<n; i++)
      min=min<(d[(1<<n)-1][i]+c[i][0]) ? min:(d[(1<<n)-1][i]+c[i][0]);
    if(min>=INF)
      fprintf(fout,"Nu exista solutie");
    else
      fprintf(fout,"%d\n",min);
    fclose(fin);
    fclose(fout);
    return 0;
}