#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>

#define NMAX 20
#define INF 0x3f3f3f3f
#define CMAX (1<<18) + 5
#define get_min(a,b) ((a)>(b)?(b):(a))

using namespace std;

typedef vector < int > ::iterator vii;
ifstream in ( "hamilton.in" );
ofstream out ( "hamilton.out" );

int Cost[NMAX][NMAX] ,N , M, Sol[CMAX][NMAX];
vector < int > G[NMAX];

int main ( void )
{
	int i , j;
	in >> N >> M;
	memset ( Cost , INF , sizeof ( Cost) );
	for ( i = 1 ; i <= M ; ++i )
	{
		int x , y , c;
		in >> x >> y >> c;
		G[y].push_back(x);
		Cost[x][y] = c;
	}
	memset ( Sol , INF , sizeof ( Sol ) );
	Sol[1][0] = 0 ; 
	for ( i = 0 ; i < ( 1 << N ) ; ++i )
		for ( j = 0 ; j < N ; ++j )
			if ( i & ( 1<<j ) )
		  for ( vii it = G[j].begin() ; it != G[j].end() ; ++it )
			if ( i & ( 1<<(*it) ))
				Sol[i][j] = get_min ( Sol[i][j] , Cost[*it][j] + Sol[i^(1<<j)][*it] );
	int Answer = INF;
	for ( vii it = G[0].begin() ; it != G[0].end() ; ++it )
		Answer = get_min ( Answer , Cost[*it][0] + Sol[(1<<N) - 1][*it] );
	(  Answer != INF ?( out << Answer ) : ( out << "Nu exista solutie") ) ;
	in.close();
	out.close();
	return 0 ;
}