#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 <vector <int>> dp(n, vector <int> ((1 << (n - 1)), INF));

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

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

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

			for (auto it : adj[i]) { 
				if ((1 << it.first) & mask)
					continue;

				int new_mask = (1 << it.first) | mask;
				dp[it.first][new_mask] = min(dp[it.first][new_mask], dp[i][mask] + 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[i][(1 << (n - 1)) - 1] + c[i][n - 1]);
	}

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

	return 0;
}