#include <stdio.h>

#define maxn 1000000000

long m,n,i,j,c[19][19],a,b,sll[300000][19],k;

int main()
{
	freopen("hamilton.in","r",stdin);
	freopen("hamilton.out","w",stdout);
	scanf("%ld%ld",&n,&m);
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			c[i][j]=maxn;
		}
	}
	for(i=1;i<=m;i++){
		scanf("%ld%ld",&a,&b);
		scanf("%ld",&c[a][b]);
	}
	int nn=1<<n;
	for(i=1;i<nn;i++){
		for(j=1;j<n;j++){
			sll[i][j]=maxn;
		}
	}
	sll[1][0]=0;
	for(i=1;i<nn;i++){
		for(j=0;j<n;j++){
			if( i != 1 && j == 0) continue;
            if (sll[i][j] == maxn) continue;
			for(k=1;k<n;k++){
				if(!(i&(1<<k)) && c[j][k]>0){
					if(sll[i][j]+c[j][k]<sll[i^(1<<k)][k]){
						sll[i^(1<<k)][k]=sll[i][j]+c[j][k];
						//printf("%ld %ld\n",sll[i^(1<<k)][k],i^(1<<k));
					}
				}
			}
		}
	}
	int sol=maxn;
	for(i=1;i<n;i++){
		if(sol>sll[nn-1][i]+c[i][0] && c[i][0]>0) sol=sll[nn-1][i]+c[i][0];
	}
	if(sol!=maxn){
		printf("%ld",sol);
	}else{
		printf("Nu exista solutie");
	}
	return 0;
}