#include<fstream>
#include<vector>

using namespace std;

#define inf 100000000
#define max_n 19

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int n , x , y , m;
int C[max_n][max_n] , D[1<<max_n][max_n];
vector<int> L[max_n];

void read(){
	
	f>>n>>m;
	
	for( int i = 1 ; i <= m ; i++ ){
		f>>x>>y;
		L[y].push_back(x);
		f>>C[x][y];
	}
	
}

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

void solve(){
	
	int i , j;
	unsigned int k;
	
	for( i = 1 ; i < (1<<n) ; i++ )
		for( j = 0 ; j < n ; j++ )
			if( i & (1<<j) )
				for( k = 0 ; k < L[j].size() ; k++ )
					if( i & (1<<L[j][k]) )
						D[i][j] = minim( D[i][j] , D[i^(1<<j)][L[j][k]] + C[L[j][k]][j] );
	
	
}

void init(){
	
	int i , j;
	
	for( i = 1 ; i < (1<<n) ; i++ )
		for( j = 0 ; j < n ; j++ )
			D[i][j] = inf;
	
	D[1][0] = 0;
}

void print(){
	
	int sol = inf;
	
	for( int i = 0 ; i < n ; i++ )
		if( C[i][0] != 0 )
			sol = minim( sol , D[(1<<n) - 1][i] + C[i][0] );
	
	if( sol == inf ){
		g<<"Nu exista solutie\n";
		return;
	}
	g<<sol<<"\n";
}

int main(){
	
	read();
	
	init();
	
	solve();
	
	print();
	
	return 0;
}