#include<stdio.h>
#include<vector>
#define NMAX 20
#define XMAX 262150 //aprox 1<<18 , limita maxima a lui n
#define INF 1<<30
using namespace std;

FILE *in,*out;
int cost[NMAX][NMAX],x,y;
vector<int> A[NMAX];
int C[XMAX][NMAX],Sol,i,j,m,n;
int main()
{
	in=fopen("hamilton.in","rt");
	out=fopen("hamilton.out","wt");
	fscanf(in,"%d %d",&n,&m);
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			cost[i][j]=INF;
	for(i=1;i<=m;i++)
	{
		fscanf(in,"%d %d",&x,&y);
		A[y].push_back(x);
		fscanf(in,"%d",&cost[x][y]);
	}
	
	for(i=0; i<1<<n ;i++)
		for(j=0;j<n;j++)
			C[i][j]=INF;
	C[1][0]=0;
	
	for(i=0; i<1<<n ;i++)
		for(j=0;j<n;j++)
			if(i & (1<<j) )
				for(int k=0;k<A[j].size();k++)
					if(i & (1<<A[j][k]))
						C[i][j] = min( C[i][j] , C[i ^ (1<<j)][ A[j][k] ] + cost[ A[j][k] ][j]); 
	Sol=INF;
	for(i=0;i<A[0].size();i++)
		Sol=min(Sol,C[(1<<n)-1][A[0][i]] + cost[A[0][i]][0]);
	if(Sol==INF)
	{
		fprintf(out,"Nu exista solutie\n");
		return 0;
	}
	fprintf(out,"%d",Sol);
	return 0;
	
}