#include <bits/stdc++.h>

using namespace std;
#define pb push_back
const int N = 1e5 + 5, INF = 1e9;

int n, m, dp[20][(1ll << 19)], ad[20][20];

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	freopen("hamilton.in", "r", stdin);
	freopen("hamilton.out", "w", stdout);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, c;
		cin >> x >> y >> c;
		ad[x][y] = c;
	}
	/// dp[i][mask] = lungimea minima a unui lant hamiltonian care se termina in nodul i si contine masca de noduri
	/// dp[i][mask] = min(dp[i][mask], dp[j][mask ^ (1ll << i)] + muchia(j, i));
	for (int i = 0; i < n; i++) {
		for (int mask = 0; mask < (1ll << n); mask++) {
			dp[i][mask] = INF;
		}
	}
	dp[0][1] = 0;
	for (int mask = 1; mask < (1ll << n); mask++) {
		for (int i = 0; i < n; i++) {
			if (mask & (1ll << i)) {
				for (int j = 0; j < n; j++) {
					if (i != j && ad[j][i] && (mask & (1ll << j))) {
						dp[i][mask] = min(dp[i][mask], dp[j][mask ^ (1ll << i)] + ad[j][i]);
					}
				}
			}
		}
	}
	int ans = INF;
	for (int i = 1; i < n; i++) {
		if (ad[i][0])
			ans = min(ans, dp[i][(1ll << n) - 1] + ad[i][0]);
	}
	cout << ans;
}