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

using namespace std;

const int INF = numeric_limits<int>::max()/2;

int keres(int conf, int veg, vector<vector<int>>& memo, const vector<vector<int>>& el, const vector<vector<int>>& beSzomszed){
	if (memo[conf][veg] != -1) {
		return memo[conf][veg];
	}

	memo[conf][veg] = INF;
	
	for (int szomszed : beSzomszed[veg]) {
		if (!(conf & (1 << szomszed))) continue;
		if (szomszed == 0 && conf != (1 << (veg)) + 1) continue; // a 0 csak akkor jo, ha ez az utolso el

		memo[conf][veg] = min(
			memo[conf][veg], 
			keres(conf ^ (1 << veg), szomszed, memo, el, beSzomszed) + el[szomszed][veg]);
	}
	return memo[conf][veg];
}

int main()
{
	ifstream fin("hamilton.in");
	ofstream fout("hamilton.out");

	int n, m;
	fin >> n >> m;

	vector<vector<int>> el(n, vector<int>(n, INF));
	vector<vector<int>> beSzomszed(n);

	for (int i = 0; i < m; ++i){
		int x, y;
		fin >> x >> y;
		beSzomszed[y].push_back(x);
		fin >> el[x][y];
	}

	vector<vector<int>> memo(1 << n, vector<int>(n, -1));
	memo[1][0] = 0;

	int legjobb = INF;
	for (int szomszed : beSzomszed[0]) {
		legjobb = min(legjobb, keres((1 << n) - 1, szomszed, memo, el, beSzomszed) + el[szomszed][0]);
	}

	if (legjobb == INF) fout << "Nu exista solutie" << endl;
	else fout << legjobb << endl;

	return 0;
}