# include <fstream>
 # include <cstring>
 # include <algorithm>
 # include <vector>
 
 # define dim 20
 # define inf 999999999
 # define pb push_back
 
 using namespace std;
 
 ifstream f("hamilton.in");
 ofstream g("hamilton.out");
 
 vector < int > a[ dim ];
 int dp[ 1 << dim ][ dim ];
 int cost[ dim ][ dim ];
 int n, m;
 int sol;
 
 void init_cost()
 {
	 int i, j;
	 
	 for ( i = 0 ; i < n ; i++ )
		 for ( j = 0 ; j < n ; j++ )
			 cost[ i ][ j ] = inf;
 }
 
 void init()
 {
	 int i, j;
	 for ( i = 0 ; i <= ( 1 << n ) ; i++ )
		 for ( j = 0 ; j < n ; j++ )
			 dp[ i ][ j ] = inf;
 }
 
 void citire()
 {
	 int i, x, y, z;
	 
	 f >> n >> m;
	 init_cost();
	 for ( i = 1 ; i <= m ; i++ )
	 {
		 f >> x >> y >> z;
		 a[ y ].pb( x );
		 cost[ x ][ y ] = z;
	 }
	 
 }
 
 void afisare()
 {
	 int i, j;
	 for ( i = 1 ; i < ( 1 << n ) ; i++ )
	 {
		 for ( j = 0 ; j < n ; j++ )
			 g << dp[ i ][ j ] << " ";
		 g << "\n";
	 }
	 g << "\n";
 }
 
 void rezolva()
 {
	 int i, j, k;
	 
	 sol = inf;
	 init();
	 
	 dp[ 1 ][ 0 ] = 0;
	 
	 for ( i = 1 ; i < ( 1 << n ) ; i++ )
		 for ( j = 0 ; j < n ; j++ )
			 if ( i & ( 1 << j) )
			  for ( k = 0 ; k < a[ j ].size(); k++ )
				 if ( i & ( 1 << a[ j ][ k ] ) )
					 dp[ i ][ j ] = min( dp[ i ][ j ], dp[ i ^ ( 1 << j ) ][ a[ j ][ k ] ] + cost[ a[ j ][ k ] ][ j ] );
	 
	 for ( i = 0 ; i < a[ 0 ].size() ; i++ )
		 sol = min( sol, dp[ ( 1 << n ) - 1 ][ a[ 0 ][ i ] ] + cost[ a[ 0 ][ i ] ][ 0 ] );
	 
	 if ( sol != inf )
		 g << sol << "\n";
	 else
		 g << "Nu exista solutie" <<"\n";
 }
 
 int main()
 {
	 citire();
	 rezolva();
	 return 0;
 }