#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,conf,nod;
int C[maxn][maxn],G[maxn][maxn+3];
int D[maxn][(1<<maxn)+3];

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

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;
		}
	}
	
	D[0][1] = 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]);
	}
	
	for ( conf = 1 ; conf < (1<<n) ; ++conf ){
		for ( nod = 0 ; nod < n ; ++nod ){
			
			if ( conf & (1<<nod) ){
				
				for ( i = 1 ; i <= G[nod][0] ; ++i ){
					int nodvcn = G[nod][i];
					
					if ( conf & (1<<nodvcn) ){
						
						if ( !(!nodvcn && conf != (1<<nod) + 1) ){
							D[nod][conf] = min(D[nod][conf],D[nodvcn][conf^(1<<nod)] + C[nodvcn][nod]);
						}
					}
				}
			}
		}
	}
	
	int best = INF;
	for ( i = 1 ; i <= G[0][0] ; ++i ){
		int fin = G[0][i];
		best = min(best,D[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;
}