# 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;

bool sing ( const int k ){
	int i;
	for ( i = 0; i < k; ++ i )
		if ( p [ i ] == p [ k ] )
			return 0;
	return 1;
}

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 ( int k ){
	if ( k == n )
		updateMinCost (  );
	else {
		int i;
		for ( i = 0; i < n; ++ i ){
			p [ k ] = i;
			if ( sing ( k ) )
				back ( k + 1 );
		}
	}
}

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;
		
	}
	
	f . close();
	
	back ( 0 );
	
	ofstream g ( "hamilton.out" );
	
	if ( cst == inf )
		g << "Nu exista solutie\n";
	else
		g << cst << '\n';
	
	g . close ();
	
	return 0;
}