# include <iostream>
# include <fstream>
# include <algorithm>
# include <vector>

using namespace std;

const int inf = 0x3f3f3f3f, MAXN = 18;

struct neighbour{
	int id, cost;
};

bool G [ MAXN ] [ MAXN ];
int C [ MAXN ] [ MAXN ];
int n, m;
int p [ MAXN + 1 ];
int cst = inf;

void updateMinCost(){
	
	int kst = 0, i;
	
	p [ n ] = p [ 0 ];
	for ( i = 0; i < n; ++ i )
		if ( ! G [ p [ i ] ] [ p [ i + 1 ] ] )
			return;
		else kst += C [ p [ i ] ] [ p [ i + 1 ] ];
	if ( kst < cst )
		cst = kst;
}

void back (){

	do
		updateMinCost (  );
	while ( next_permutation ( p, p + n ) );
}

int main(){
	
	int i, node1, node2, kst;
	
	ifstream f ( "hamilton.in" );
	
	f >> n >> m;
	
	for ( i = 0; i < m; ++ i ){
	
		f >> node1 >> node2 >> kst;
		G [ node1 ] [ node2 ] = true;
		C [ node1 ] [ node2 ] = kst;
		
	}
	
	for ( i = 0; i < n; ++ i )
		p [ i ] = i;
	
	f . close();
	
	back ();
	
	ofstream g ( "hamilton.out" );
	
	if ( cst == inf )
		g << "Nu exista solutie\n";
	else
		g << cst << '\n';
	
	g . close ();
	
	return 0;
}