#include<stdio.h>
#define INF 1000000000
long a[19][19]={0},lg[19],d,x[19];
int n,v[19]={0},m,j,k;
long ham(int k,int j)
{if(k-1==n&&a[j][1]&&lg[n]+a[j][1]<x[n])
       return lg[n]+a[j][1];
for(int i=2;i<=n;i++)
if(!v[i]&&a[j][i]&&(lg[k]=lg[k-1]+a[j][i])<x[n])
       {v[i]=1;
       x[k]=ham(k+1,i);
       if(x[k-1]<x[k])
              if(x[k]<x[n])
                       if(lg[k]<x[k])
                                x[n]=lg[k];
                       else
                                x[n]=x[k];
              else
                       x[k]=lg[k];
       v[i]=0;}
return x[n];}
               
int main()
{freopen("hamilton.in","r",stdin);
freopen("hamilton.out","w",stdout);
scanf("%d%d",&n,&m);
while(m--)
       {scanf("%d%d%ld",&j,&k,&d);
       a[j+1][k+1]=d;}
lg[1]=0;
x[1]=x[n]=INF;
if((d=ham(2,1))==INF)
       printf("Nu exista solutie");
else
       printf("%ld",d);
fclose(stdin);
fclose(stdout);
return 0;}