#include <cstdio>
#include <cstring> 
#include <vector>
#include <algorithm>

using namespace std;

#define file_in "hamilton.in"
#define file_out "hamilton.out"

#define Nmax 20
#define Mmax 272020

int n,m;
vector<int> G[Nmax];
int C[Nmax][Nmax];
int CC[Mmax][Nmax];
int rez;

int main()
{
	int i,j,k;
	int a,b,c;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d%d", &n, &m);
	
	for (i=0;i<n;++i)
		 for (j=0;j<n;++j)
			  C[i][j]=0x3f3f3f3f;
		 
	for (i=1;i<=m;++i)
    {
		scanf("%d%d%d", &a, &b, &c);
		C[a][b]=c;
		G[b].push_back(a);
	}
	
	for (i=0;i<(1<<n);++i)
		 for (j=0;j<n;++j)
			  CC[i][j]=0x3f3f3f3f;
		 
	CC[1][0]=0;
	for (i=0;i<(1<<n);++i)
		 for (j=0;j<n;++j)
			  if (i&(1<<j))
				   for (k=0;k<G[j].size();++k)
					    if (i&(1<<G[j][k]))
							CC[i][j]=min(CC[i][j],C[G[j][k]][j]+CC[i^(1<<j)][G[j][k]]);
	
    rez=0x3f3f3f3f;						
	for (i=0;i<G[0].size();++i)
		 rez=min(rez,CC[(1<<n)-1][G[0][i]]+C[G[0][i]][0]);
	if (rez==0x3f3f3f3f) 
		printf("Nu exista  solutie");
	else
		printf("%d", rez);
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;

}