#include<stdio.h>
#define N 1000000000
long c[262145][19],w[19][19],i,j,d,k,v;
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),w[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]=N;
       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])
              {v=N;
              for(p=0;p<t;p++)
              if(w[u[p]][u[r]]&&v>w[u[p]][u[r]]+c[j^(1<<u[r])][u[p]])
                      v=w[u[p]][u[r]]+c[j^(1<<u[r])][u[p]];
              c[j][u[r]]=v;}}
v=N;
for(j=0;j<n;j++)
if(w[j][0]&&v>c[(1<<n)-1][j]+w[j][0])
      v=c[(1<<n)-1][j]+w[j][0];
if(v==N)
      printf("Nu exista solutie");
else
      printf("%ld",v);
return 0;}