#include<stdio.h>
#include<vector>
#define Nmax 20
#define Inf 1<<20
#define Min(a,b) a<b ? a : b
using namespace std;

int Cost[Nmax][Nmax],i,j,n,N,k,m,a,b,v,M,Sol,C[1<<Nmax][Nmax];
vector<int> V[Nmax];

int main()
{
	freopen("hamilton.in","r",stdin);
	freopen("hamilton.out","w",stdout);
	
	scanf("%d %d",&n,&m);
	
	N=(1<<n)-1;
	
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			Cost[i][j]=Inf;
		
	for(i=1;i<=m;i++)
	{
		scanf("%d %d",&a,&b);
		
		V[b].push_back(a);
		
		scanf("%d",&Cost[a][b]);
	}
	
	for(i=0;i<=N;i++)
		for(j=0;j<n;j++)
			C[i][j]=Inf;
		
	C[1][0]=0;	
	
	for(i=0;i<=N;i++)
		
		for(j=0;j<n;j++)
		
			if( (i>>j) & 1 )
			{
				M=V[j].size();
				
				for(k=0;k<M;k++)
				{
					v=V[j][k];
					
					if( (i>>v) & 1 )
						C[i][j] = Min ( C[i][j], C[i^(1<<j)][v] + Cost[v][j] ) ;
				}
			}
		
	Sol=Inf;
	M=V[0].size();
	
	for(i=0;i<M;i++)
	{
		v=V[0][i];
		Sol = Min ( Sol, C[N][v] + Cost[v][0] ) ;
	}
	
	if(Sol==Inf) printf("Nu exista solutie");
	else printf("%d",Sol);
	return 0;
}