#include<iostream>
#include<fstream>
#include<vector>
std::ifstream in("hamilton.in");
std::ofstream out("hamilton.out");
using namespace std;
vector<int>g[20];
int n, m, ad[20][20];
int main() {
	in >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) ad[i][j] = 0x3F3F3F3F;
	while (m--) {
		int u, v, c;
		in >> u >> v >> c;
		g[u].push_back(v);
		ad[v][u] = c;
	}
	vector<vector<int>> dp(1 << n, vector<int>(n, 0x3F3F3F3F));
	dp[1][0] = 0;
	for (int mask = 3; mask < (1 << n); mask += 2) {
		for (int i = 1; i < n; i++)
			if (mask & (1 << i))
				for (int j : g[i])
					dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][j] + ad[j][i]);
	}
	int sol = 0x3F3F3F3F;
	for (int i = 1; i < n; i++)
		sol = min(sol, dp[(1 << n) - 1][i] + ad[i][0]);
	if (sol == 0x3F3F3F3F) out << "Nu exista solutie";
	else out << sol;
	return 0;
}