#include <bits/stdc++.h>

using namespace std;

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

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

	fin >> n >> m;

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

		fin >> x >> y >> c;

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

		if (y == 0) {
			cost[x] = c;
		}
	}

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

	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 = 1e9 + 1;

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

	fout << sol << " ";

	return 0;
}