#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;

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

#define nmax 18
#define inf 0x3f3f3f3f

int i, j, n, m;
int a, b, c;
int ans;

int cost[nmax][nmax];
int dp[nmax][(1 << nmax) + 3];

struct nod {
	int u;
	nod *next;
};
nod *v[nmax];

void add(int i, int j) {
	nod *p = new nod;
	p->u = j;
	p->next = v[i];
	v[i] = p;
}

int main() {
	fin >> n >> m;
	memset(cost, inf, sizeof(cost));
	memset(dp, inf, sizeof(dp));
	for (i = 1; i <= m; ++i) {
		fin >> a >> b >> cost[a][b];
		add(b, a);
	}
	int lim = (1 << n);
	for (i = 0; i < n; ++i) 
		dp[i][(1 << i)] = 0;
	for (j = 2; j < lim; ++j) {
		for (i = 0; i < n; ++i) {
			if (i == 1) continue;
			for (nod *it = v[i]; it; it = it->next) {
				if ((j & (1 << i)) && (j & (1 << it->u))) {
					dp[i][j] = min(dp[i][j], dp[it->u][j ^ (1 << i)] + cost[it->u][i]);
				}
			}
		}
	}
	ans = inf;
	for (i = 0; i < n; ++i)
		if (i == 1) continue;
		else
			ans = min(ans, dp[i][lim - 1] + cost[i][1]);
	fout << ans << '\n';
	return 0;
}