#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

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

	int n, m;
	in >> n >> m;

	if (n == 1) {
		out << 0 << endl;
		return 0;
	}

	vector <vector <int>> c(n, vector <int>(n, 0));
	vector <vector <pair <int, int>>> adj(n);
	for (int i = 0; i < m ; ++i) {
		int x, y;
		in >> x >> y;
		in >> c[x][y];
		adj[x].push_back({y, c[x][y]});
	}

	vector <int> p2(n, 0);
	p2[0] = 1;
	for (int i = 1; i < n ; ++i)
		p2[i] = p2[i - 1] << 1;
	vector <vector <int>> dp(p2[n - 1], vector <int> (n, INF));

	for (int i = 0; i < n - 1 ; ++i)
		if (c[n - 1][i]) {
			dp[p2[i]][i] = c[n - 1][i];
			//cerr << i << endl;
		}

	for (int mask = 1; mask < p2[n - 1] ; ++mask) {
		for (int i = 0; i < n - 1 ; ++i) {
			if (!(p2[i] & mask))
				continue;

			if (dp[mask][i] == INF)
				continue;

			for (auto it : adj[i]) { 
				if (it.first == n - 1)
					continue;

				if (p2[it.first] & mask)
					continue;

				int new_mask = p2[it.first] | mask;
				dp[new_mask][it.first] = min(dp[new_mask][it.first], dp[mask][i] + it.second);
				//cerr << new_mask << " " << dp[j][new_mask] << endl;
			}
		}
	}

	int mn = INF;

	for (int i = 0; i < n - 1 ; ++i) {
		if (c[i][n - 1] == 0)
			continue;
		mn = min(mn, dp[p2[n - 1] - 1][i] + c[i][n - 1]);
	}

	if (mn == INF)
		out << "Nu exista solutie" << endl;
	else
		out << mn << endl;

	return 0;
}