#include <bits/stdc++.h>

using namespace std;

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

int dp[260001][18], n, m;
vector <pair <int, int>> g[100001];
int main () {

	cin >> n >> m;

	for (int i = 1; i <= m; i++) {
		int x, y, c;

		fin >> x >> y >> c;

		g[y].push_back({x, c});
	}

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

	dp[1][0] = 0;

	for (int config = 3; config < (1 << n); config++) {
		for (int i = 1; i < n; i++) {
			if (config & (1 << i)) {
				for (auto j : g[i]) {
					dp[config][i] = min(dp[config][i], dp[config ^ (1 << i)][j.first] + j.second);
				}
			}
		}
	}

	int sol = 1e6;

	for (int i = 1; i < n; i++) {
		if (g[i][0].first) {
			sol = min(sol, dp[(1 << n) - 1][i] + g[i][0].second);
		}
	}

	fout << sol << " ";

	return 0;
}