#include <bits/stdc++.h>

using namespace std;
const int MASK = (1 << 18) + 1, NMAX = 20;

int n, x, y, c, m, ad[NMAX][NMAX];
vector<int> g[NMAX];

signed main() {
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
	cin >> n >> m;
	vector<vector<int>> ad(n, vector<int>(n, 1e9));
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> c;
		g[y].push_back(x);
		ad[x][y] = c;
	}
	vector<vector<int>> dp(1 << n, vector<int>(n, 1e9));
	dp[1][0] = 0;
	for (int mask = 3; mask < (1 << n); mask += 2) {
		for (int i = 1; i < n; i++) {
			if (mask & (1 << i)) {
				for (auto intra : g[i])
					dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][intra] + ad[intra][i]);
			}
		}
	}
	int ans = 1e9;
	for (int i = 1; i < n; i++)
		ans = min(ans, dp[(1 << n) - 1][i] + ad[i][0]);
	cout << ans;
	return 0;
}