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