#include <cstdio>
#include <algorithm>
using namespace std;

inline int next_int() {
	int d;
	scanf("%d", &d);
	return d;
}

const int V = 18;
const int E = 18 * 17 + 1;

int n, m;
int ec, eb[V], eu[E], ev[E], ew[E], en[E];
bool seen[18][1 << 18];
int dp[18][1 << 18];

int f(int u, int mask) {
	if (mask == (1 << n) - 1) {
		return 0;
	}
	if (seen[u][mask]) {
		return dp[u][mask];
	}
	seen[u][mask] = true;
	dp[u][mask] = 2e9;
	for (int e = eb[u]; e; e = en[e]) {
		int v = ev[e];
		if ((mask & (1 << v)) == 0) {
			dp[u][mask] = min(dp[u][mask], ew[e] + f(v, mask | (1 << v)));
		}
	}
	return dp[u][mask];
}

int main() {
	freopen("hamilton", "r", stdin);
	freopen("hamilton.out", "w", stdout);
	n = next_int();
	m = next_int();
	for (int i = 0; i < m; i++) {
		int u = next_int();
		int v = next_int();
		int w = next_int();
		ec++;
		eu[ec] = u;
		ev[ec] = v;
		ew[ec] = w;
		en[ec] = eb[u];
		eb[u] = ec;
	}
	printf("%d", f(0, 0));
	return 0;
}