#include<fstream>
#include<vector>
using namespace std;

ifstream cin("hamilton.in");
ofstream cout("hamilton.out");

vector<vector<int>> dp;
vector<vector<pair<int, int>>> graph;
vector<vector<pair<int, int>>> rgraph;

int main() {
	int i, j, nr, n, m, u, v, c, pw;

	cin >> n >> m;

	pw = (1 << n);
	dp = vector<vector<int>>(pw + 1, vector<int>(n, INT32_MAX));
	dp[1] = vector<int>(n, 0);
	graph.resize(n);
	rgraph.resize(n);

	for (i = 0; i < m; i++) {
		cin >> u >> v >> c;
		graph[u].push_back({ v,c });
		rgraph[v].push_back({ u,c });
	}

	for (int p = 1; p < pw; p++) {
		for (i = 0; i < n; i++) {
			if (p & (1 << i)&& dp[p][i]!=INT32_MAX) {
				for (auto v : graph[i]) {
					if (!(p & (1 << v.first)) && dp[p][i] + v.second < dp[(p | (1 << v.first))][v.first]) {
						dp[(p | (1 << v.first))][v.first] = dp[p][i] + v.second;
					}
				}
			}
		}
	}

	int res = INT32_MAX;

	for (auto v : rgraph[0]) {
		if (dp[pw - 1][v.first] != INT32_MAX) {
			res = min(res, dp[pw - 1][v.first] + v.second);
		}
	}

	cout << res;

	return 0;
}