#include <fstream>
#include <iostream>
#include <vector>

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int INF = 1e9;
int main() {
	int n, m;
	fin >> n >> m;

	vector<vector<int>> d(n + 1, vector<int>(n + 1, INF));
	for (int i = 1; i <= m; i++) {
		int a, b, dist;
		fin >> a >> b >> dist;
		a++;
		b++;

		d[a][b] = dist;
	}

	vector<vector<int>> dp(1 << n, vector<int>(n + 1, INF));
	dp[1][1] = 0;
	for (int mask = 0; mask < (1 << n); mask++) {
		for (int i = 1; i <= n; i++) {
			if (mask & (1 << (i - 1))) {
				for (int j = 1; j <= n; j++) {
					if (i == j || d[j][i] == INF)
						continue;

					if (mask & (1 << (j - 1))) {
						dp[mask][i] =
							min(dp[mask][i],
								dp[mask ^ (1 << (i - 1))][j] + d[j][i]);
					}
				}
			}
		}
	}

	int ans = INF;
	for (int i = 1; i <= n; i++) {
		ans = min(ans, dp[(1 << n) - 1][i] + d[i][1]);
	}

	if (ans == INF)
		fout << "Nu exista solutie";
	else
		fout << ans;
}