#include<stdio.h>

#define maxn 18
#define INF (1<<29)

FILE*f=fopen("hamilton.in","r");
FILE*g=fopen("hamilton.out","w");

int n,m,i,j,x,y;
int C[maxn][maxn],G[maxn][maxn+3];
int D[maxn][1<<maxn];

inline int min ( int a , int b ){
	return a <= b ? a : b;
}

int rec ( int nod , int conf ){
	
	if ( D[nod][conf] != INF )	return D[nod][conf];
	
	for ( int i = 1 ; i <= G[nod][0] ; ++i ){
		int nodvcn = G[nod][i];
		
		if ( conf & (1<<nodvcn) ){
			
			if ( !nodvcn && conf != (1<<nod) + 1 ){
				continue ;
			}
			
			D[nod][conf] = min(D[nod][conf],rec(nodvcn,conf-(1<<nod)) + C[nodvcn][nod]);
		}
	}
	
	return D[nod][conf]; 
}

int main () {
	
	fscanf(f,"%d %d",&n,&m);
	
	for ( i = 0 ; i < n ; ++i ){
		for ( j = 0 ; j < (1<<n) ; ++j ){
			D[i][j] = INF;
		}
		for ( j = 0 ; j < n ; ++j ){
			C[i][j] = INF;
		}
	}
	
	for ( i = 0 ; i < n ; ++i ){
		D[i][1<<i] = 0;
	}
	
	for ( i = 1 ; i <= m ; ++i ){
		fscanf(f,"%d %d",&x,&y);
		G[y][++G[y][0]] = x;
		fscanf(f,"%d",&C[x][y]);
	}
	
	int best = INF;
	for ( i = 1 ; i <= G[0][0] ; ++i ){
		int fin = G[0][i];
		best = min(best,rec(fin,(1<<n)-1) + C[fin][0]);
	}
	
	if ( best != INF ){
		fprintf(g,"%d\n",best);
	}
	else{
		fprintf(g,"Nu exista solutie\n");
	}
	
	fclose(f);
	fclose(g);
	
	return 0;
}