#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream cin("hamilton.in");
ofstream cout("hamilton.out");
int n, m, dp[262149][20];
struct much {
	int y, c;
};
vector<vector<much>>gr;
int main() {
	cin >> n >> m;
	for (int i = 0; i <= n; i++) {
		gr.emplace_back(vector<much>());
	}
	for (int i = 1; i <= m; i++) {
		int x, y, c;
		cin >> x >> y >> c;
		x++;
		y++;
		gr[x].push_back({ y, c });
	}
	int msk = (1 << n) - 1;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= msk; j++) {
			dp[j][i] = 1e9;
		}
	}
	dp[1][1] = 0;
	for (int i = 2; i <= msk; i++) {
		for (int j = 1; j <= n; j++) {
			if (((1 << (j - 1)) & i) == 0) {
				continue;
			}
			else {
				for (int k = 0; k < gr[j].size(); k++) {
					int y = gr[j][k].y - 1;
					int c = gr[j][k].c;
					if ((i & (1 << y)) == 0) {
						continue;
					}
					else {
						int prev = (i ^ (1 << y));
						dp[i][y + 1] = min(dp[i][y + 1], dp[prev][j] + c);
					}
				}
			}
		}
	}
	int ans = 1e9;
	int c;
	for (int i = 1; i <= n; i++) {
		c = 1e9;
		for (int j = 0; j < gr[i].size(); j++) {
			if (gr[i][j].y == 1) {
				c = gr[i][j].c;
				break;
			}
		}
		ans = min(ans, dp[msk][i] + c);
	}
	if (ans == 1e9) {
		cout << "Nu exista solutie";
		return 0;
	}
	cout << ans;
}