#include<cstdio>
int c[262145][19],w[19][19],i,j,d,k,v,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%d",&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]=1000000000;
       for(l=t=0,k=j;k;k>>=1,l++)
       if(k&1)
              u[t++]=l;
       for(r=0;r<t;r++)
       if(u[r])
              {v=1000000000;
              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=1000000000;
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==1000000000)
      printf("Nu exista solutie");
else
      printf("%d",v);
return 0;}