#include<stdio.h>
#define NMAX 2000000000
int d[20][524288],v[20][20];

int main()
{
freopen("hamilton.in","r",stdin);
freopen("hamilton.out","w",stdout);
int n,i,m,mas,mod,x,y,c,min=NMAX,no;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
	{
	scanf("%d%d%d",&x,&y,&c);
	v[x][y]=c;
	}
no=(1<<n);
for(i=1;i<n;i++)
	if(v[0][i]>0)
		d[i][1+(1<<i)]=v[0][i];
for(mas=3;mas<no;mas=mas+2)
	for(mod=1;mod<n;mod++)
		if((mas & (1<<mod)) && d[mod][mas]!=0)
			{
			for(i=1;i<n;i++)
				if(v[mod][i]!=0)
					{
					if((mas&(1<<i))==0)
						d[i][mas+(1<<i)]=d[mod][mas]+v[mod][i];
					}
			}
		
for(i=0;i<n;i++)
	if(d[i][no-1]!=0)
		if(v[i][0]>0)
			if(min>d[i][no-1]+v[i][0])
				min=d[i][no-1]+v[i][0];
if(min==NMAX)
	printf("Nu exista solutie");
else
	printf("%d",min);
return 0;
}