#include <vector>
#include <fstream>
#include <cstdlib>
#define N_MAX 19
#define oo 1<<25
#define pr pair< int, int >

using namespace std;
int H[1<<N_MAX][N_MAX], C[N_MAX][N_MAX];
vector< int > G[N_MAX], Gt[N_MAX];
vector< int >::const_iterator it, iend;
int main( void )
{
	int N, M, x, y, till, i, j, k;
	ifstream in( "hamilton.in" );
	for( in>>N>>M; M; --M )
	{
		in>>x>>y;
		in>>C[x][y];
		Gt[y].push_back( x );
	}
	till=1<<N;
	for( i=0; i < till; ++i )
		for( j=0; j < N; ++j )
			H[i][j]=oo;
	H[1][0]=0;
	for( i=0; i < till; ++i )
		for( j=0, k=1; j < N; k*=2, ++j )
			if( i&k )
			{
				x=i^k;
				for( it=Gt[j].begin(), iend=Gt[j].end(); it < iend; ++it )
					if( x & ( 1<<(*it) ) )
						H[i][j]=min( H[i][j], H[x][*it]+C[*it][j] );
			}
	for( i=oo, till-=1, it=Gt[0].begin(), iend=Gt[0].end(); it < iend; ++it )
		i=min( i, H[till][*it]+C[*it][0] );
	ofstream out( "hamilton.out" );
	if( i == oo )
		out<<"Nu exista solutie\n";
	else out<<i<<'\n';
	return EXIT_SUCCESS;
}