#include <stdio.h>
#include <stdlib.h>
#define MAXN 18
#define MAXM 153
#define INF 1000000000
int d[(1<<MAXN)][MAXN],nod[MAXM+1],c[MAXM+1],next[MAXM+1],ind[MAXM+1];
int main(){
    FILE*fi,*fout;
    int n,m,i,j,p,y,min;
    fi=fopen("hamilton.in" ,"r");
    fout=fopen("hamilton.out" ,"w");
    fscanf(fi,"%d%d" ,&n,&m);
    for(i=1;i<=m;i++){
        fscanf(fi,"%d%d%d" ,&nod[i],&y,&c[i]);
        next[i]=ind[y];
        ind[y]=i;
    }
    for(i=0;i<(1<<n);i++)
        for(j=0;j<n;j++)
          d[i][j]=INF;
    d[1][0]=0;
    for(i=0;i<(1<<n);i++)
        for(j=0;j<n;j++)
           if((i&(1<<j))>0){
               p=ind[j];
               while(p>0){
                    if(d[i][j]>d[i^(1<<j)][nod[p]]+c[p])
                       d[i][j]=d[i^(1<<j)][nod[p]]+c[p];
                    p=next[p];
               }
           }
    p=ind[0];
    min=INF;
    while(p>0){
        if(min>d[(1<<n)-1][nod[p]]+c[p])
            min=d[(1<<n)-1][nod[p]]+c[p];
        p=next[p];
    }
    if(min==INF)
        fprintf(fout,"NU exista solutie\n");
    else
        fprintf(fout,"%d" ,min);
    fclose(fi);
    fclose(fout);
    return 0;
}