#include <iostream>
#include <fstream>
#include <vector>
#define INF (1 << 29)

using namespace std;

int Hamilton(const vector<vector<int>>& cost) {
	int n = cost.size();
	vector<vector<int>> dp((1 << n), vector<int>(n, INF));
	dp[1][0] = 0;

	for (int mask = 1; mask < dp.size(); mask++) {
		if ((mask & 1) == 0) { continue; }
		for (int i = 0; i < n; i++) {
			// cerr << mask << " " << i << " " << dp[mask][i] << endl;
			if ((mask & (1 << i)) == 0) { continue; }
			for (int j = 0; j < n; j++) {
				if ((mask & (1 << j)) != 0) { continue; }
				dp[mask | (1 << j)][j] = min(
					dp[mask | (1 << j)][j], 
					dp[mask][i] + cost[i][j]);
			}
		}
	}

	int ans = INF;
	for (int i = 0; i < n; i++) {
		// cerr << i << " " << dp[(1 << n) - 1][i] << " " << ans << '\n';
		ans = min(ans, dp[(1 << n) - 1][i] + cost[i][0]);
	}

	return (ans == INF ? -1 : ans);
}

int main() {
	ifstream in("hamilton.in");
	ofstream out("hamilton.out");
	int n, m; in >> n >> m;
	vector<vector<int>> cost(n, vector<int>(n, INF));
	for (int i = 0; i < m; i++) {
		int a, b, c; in >> a >> b >> c;
		cost[a][b] = c;
	}

	int ans = Hamilton(cost);
	if (ans == -1) {
		out << "Nu exista solutie\n";
	} else {
		out << ans << "\n";
	}

	return 0;
}