#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));
	for (int i = 0; i < m ; ++i) {
		int x, y;
		in >> x >> y;
		in >> c[x][y];
	}

	vector <vector <int>> dp(n, vector <int> ((1 << n), INF));
	dp[0][1] = 0;

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

			for (int j = 0; j < n ; ++j) {
				if ((1 << j) & mask || c[i][j] == 0)
					continue;

				int new_mask = (1 << j) | mask;
				dp[j][new_mask] = min(dp[j][new_mask], dp[i][mask] + c[i][j]);
			}
		}
	}

	int mn = INF;

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

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

	return 0;
}