#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
struct muchie{
	int x, c;
};
int dp[( 1 << 18 )][18];
vector <muchie> v[20];
int main(){
	int n, m, i, k, j, x, y, c, ras;
	ifstream fin( "hamilton.in" );
	ofstream fout( "hamilton.out" );
	fin >> n >> m;
	for( i = 0; i < m; i++ ){
		fin >> x >> y >> c;
		v[y].push_back( { x, c } );
	}
	for( i = 0; i < ( 1 << n ); i++ ){
		for( j = 0; j < n; j++ ){
			dp[i][j] = INT32_MAX / 2;
		}
	}
	dp[1][0] = 0;
	for( i = 0; i < ( 1 << n ); i++ ){
		for( j = 1; j < n; j++ ){
			for( k = 0; k < v[j].size(); k++ ){
				if( ( i | ( 1 << v[j][k].x ) ) == i ){
					dp[i][j] = min(dp[i ^ ( 1 << j )][v[j][k].x] + v[j][k].c, dp[i][j]);
					//cout << i << ' ' << j << ' ' << v[j][k].x << ' ' << ( i ^ j ) << ' ' << dp[i][j] << '\n';
				}
			}
			//cout << i << ' ' << j << ' ' << dp[i][j] << '\n';
		}
	}
	ras = INT32_MAX / 2;
	for( i = 0; i < v[0].size(); i++ ){
		ras = min( dp[( 1 << n ) - 1][v[0][i].x] + v[0][i].c, ras );
	}
	if( ras == INT32_MAX / 2 ){
		fout << "Nu exista solutie";
	}
	else{
		fout << ras;
	}
	return 0;
}