#include<cstdio>
#include<vector>
#include<utility>
#define first V
#define second C
#define N 17
#define M 1<<17
#define oo 20000000
using namespace std;
int n,m,x,y,c,a[N][M],v[N+1][N+1],sol=oo,p,q;
int main()
{
	int i,j,k;
	freopen("hamilton.in","r",stdin);
	freopen("hamilton.out","w",stdout);
	scanf("%d%d", &n, &m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d", &x, &y, &c);
		v[x][y]=c;
	}
	for(i=0;i<n-1;i++)
		if(v[n-1][i])a[i][1<<i]=v[n-1][i];
	int m=(1<<(n-1))-1;
	for(i=1;i<m;i++)
		for(j=0;j<n-1;j++)
			if(a[j][i])
				for(k=0;k<n-1;k++)
				{
					if(!v[j][k])continue;
					if(i&(1<<k))continue;
					p=i|(1<<k);
					q=a[j][i]+v[j][k];
					if(!a[k][p]){a[k][p]=q;continue;}
					if(q<a[k][p])a[k][p]=q;
				}
	for(i=0;i<n-1;i++)
		if(a[i][m]&&v[i][n-1])
			sol=min(sol,a[i][m]+v[i][n-1]);
	if(sol==oo)
		printf("Nu exista solutie");
	else
		printf("%d", sol);
	return 0;
}