#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;
FILE *f1=fopen("hamilton.in","r");
FILE *f2=fopen("hamilton.out","w");
struct nod{
    int inf;
    nod *urm;
}*L[20];
int cost[20][20],i,j,inf=100000000,c[262150][20],sol,n,m;
void adaugsf(nod *&vf,int val){
     nod *q;
     q=new nod;
     q->inf=val;
     q->urm=vf;
     vf=q;
}
void cit(){
    fscanf(f1,"%d%d",&n,&m);
    int i,a,b,c;
    for (i=0;i<=n-1;i++)
        L[i]=0;
    for (i=1;i<=m;i++){
        fscanf(f1,"%d%d%d",&a,&b,&c);
        adaugsf(L[b],a);
        cost[a][b]=c;
    }
    fclose(f1);
}
int calc(int putere,int nd){
    nod *q;
    if (c[putere][nd]==-1){
        c[putere][nd]=inf;
        q=L[nd];
        while(q!=0){
            if (putere & (1<<q->inf)){
                if (q->inf==0 && putere!=(1<<nd)+1)
                    q=q->urm;
                  else{
                c[putere][nd]=min(c[putere][nd],calc(putere ^ (1<<nd),q->inf)+cost[q->inf][nd]);
                q=q->urm;
                  }
            }
              else
                q=q->urm;
        }
    }
    return c[putere][nd];
}
int main(){
   for (i=0;i<n;i++)
    for (j=0;j<n;j++)
       cost[i][j]=inf;
   memset(c,-1,sizeof(c));
   cit();
   sol=inf;
   c[1][0]=0;
   nod *q;
   q=L[0];
   while(q!=0){
      sol=min(sol,calc((1<<n)-1,q->inf)+cost[q->inf][0]);
      q=q->urm;
   }
   if (sol==inf) fprintf(f2,"Nu exista solutie");
     else
        fprintf(f2,"%d",sol);
   fclose(f2);
   return 0;
}