#include<stdio.h>
#include<algorithm>

#define INF (1<<29)

using namespace std;

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

int n,m;
int D[18][1<<18],G[18][18],C[18][18];

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

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