#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
struct muchie{
	int y, c;
};
int f[20], trecut, min_cost, cost, n;
vector <muchie> v[20];
void solve(int x){
	int i;
	if( cost >= min_cost ){
		return;
	}
	//cout << x << ' ' << trecut << ' ' << cost << '\n';
	if( x == 0 && trecut == n + 1 ){
		min_cost = min( min_cost, cost );
		return;
	}
	for( i = 0; i < v[x].size(); i++ ){
		if( f[v[x][i].y] == 0 ){
			cost += v[x][i].c;
			f[v[x][i].y] = 1;
			trecut++;
			solve( v[x][i].y );
			trecut--;
			f[v[x][i].y] = 0;
			cost -= v[x][i].c;
		}
	}
}
int main(){
	int m, i, x, y, c;
	ifstream fin( "hamilton.in" );
	ofstream fout( "hamilton.out" );
	fin >> n >> m;
	for( i = 0; i < m; i++ ){
		fin >> x >> y >> c;
		v[x].push_back( { y, c } );
	}
	min_cost = INT32_MAX;
	trecut = 1;
	cost = 0;
	solve( 0 );
	if( min_cost == INT32_MAX ){
		fout << "Nu exista solutie";
	}
	else{
		fout << min_cost;
	}
	return 0;
}