#include <bits/stdc++.h>

using namespace std;
//#define int long long

const long long N = 19, NUM_STATES = 1 << N;
int dp[NUM_STATES][N]; // ajung in nodul j cu configuratia i unde i este binar
int x, y, c, n, m;
int mc[N][N];

int main() {
	freopen("hamilton.in", "r", stdin);
	freopen("hamilton.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	while (m--) {
		cin >> x >> y >> c;
		mc[x][y] = c;
	}

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

	for (int _ = 1; _ <= n; ++_) {
		for (int nod = 0; nod < n; ++nod) {
			for (int i = 0; i < n; ++i) {
				if (mc[nod][i]) { // nod->i
					for (int mask = 1; mask < 1 << n; ++mask) {
						if (((1 << nod & mask) && (1 << i & mask) == 0)
							&& dp[mask | 1 << i][i] > dp[mask][nod] + mc[nod][i]) {

							dp[mask | 1 << i][i] = dp[mask][nod] + mc[nod][i];
						}
					}
				}
			}
		}

	}

	int mn = 10000000;
	for (int i = 0; i < n; ++i) {
		if (!mc[i][0]) continue;
		mn = min(dp[(1 << n) - 1][i] + mc[i][0], mn);
	}

	cout << mn;

	return 0;
}