#include<stdio.h>
#define INF 1000000000
long c[262145][19],cost[19][19]={0},i,j,d,k,min;
int u[19],n,m,a,b,r,p,t,l;          
int main()
{freopen("hamilton.in","r",stdin);
freopen("hamilton.out","w",stdout);
scanf("%d%d",&n,&m);
while(m--)
       {scanf("%d%d%ld",&a,&b,&d);
       cost[a][b]=d;}
for(j=0;j<(1<<n);j++)
       {for(i=0;i<n;i++)
       if(j==(1<<i))
              c[j][i]=0;
       else
              c[j][i]=INF;
       for(l=0,t=0,k=j;k;k>>=1,l++)
       if(k&1)
              u[t++]=l;
       for(r=0;r<t;r++)
       if(u[r]!=0)
              {min=INF;
              for(p=0;p<t;p++)
              if(cost[u[p]][u[r]]&&min>cost[u[p]][u[r]]+c[j^(1<<u[r])][u[p]])
                      min=cost[u[p]][u[r]]+c[j^(1<<u[r])][u[p]];
              c[j][u[r]]=min;}}
min=INF;
for(j=0;j<n;j++)
if(cost[j][0]&&min>c[(1<<n)-1][j]+cost[j][0])
      min=c[(1<<n)-1][j]+cost[j][0];
if(min==INF)
      printf("Nu exista solutie");
else
      printf("%ld",min);
fclose(stdin);
fclose(stdout);
return 0;}