#include <bits/stdc++.h>

using namespace std;
//#define int long long

const long long N = 19, NUM_STATES = 1 << N;
int dp[NUM_STATES][N]; // ajung in nodul j cu configuratia i unde i este binar
int x, y, c, n, m;
int mc[N][N];

int main() {
	freopen("hamilton.in", "r", stdin);
	freopen("hamilton.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	while (m--) {
		cin >> x >> y >> c;
		mc[x][y] = c;
	}

	for (long long i = 0; i < 1 << n; ++i) {
		for (int j = 0; j < n; ++j) {
			dp[i][j] = 1e8;
		}
	}
	dp[1][0] = 0;


	for (long long mask = 1; mask < 1 << n; ++mask) {
		for (int from = 0; from < n; ++from) {
			if (mask & 1 << from) {
				for (int to = 0; to < n; ++to) {
					if (!(mask & 1 << to) && mc[from][to]) {
						dp[mask | 1 << to][to] = min(dp[mask | 1 << to][to], dp[mask][from] + mc[from][to]);
					}
				}
			}
		}
	}

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

	if (mn == 10000000)
		cout << "Nu exista solutie";
	else
		cout << mn;

	return 0;
}