#include<stdio.h>
#define INF 1000000000
long a[19][19]={{0}},lg=0,lgmin=INF,d;
int n,t[19],v[19]={0},m,i,j,k;

void ham(int k)
{int i;
if(k-1==n&&a[t[n]][1]&&lg+a[t[n]][1]<lgmin)
       lgmin=lg+a[t[n]][1];
for(i=2;i<=n;i++)
if(a[t[k-1]][i]&&!v[i])
       {t[k]=i;
       v[i]=1;
       lg+=a[t[k-1]][i];
       if(lg<=lgmin)
               ham(k+1);
       v[i]=0;
       lg-=a[t[k-1]][i];}}
               
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;}
t[1]=1;
ham(2);
if(lgmin==INF)
       printf("Nu exista solutie");
else
       printf("%ld",lgmin);
fclose(stdin);
fclose(stdout);
return 0;}