#include <cstdio>
#include <vector>

using namespace std;

#define NMAX 20
#define PMAX 262150
#define INF 0x3f3f3f3f

int V[NMAX][PMAX], C[NMAX][NMAX], cfg, sol, n, m, i, x, y, c;
vector <int> G[NMAX];
vector <int>::iterator it;

int main () {
	
	freopen ("hamilton.in", "r", stdin);
	freopen ("hamilton.out", "w", stdout);
	
	scanf ("%d %d", &n, &m);
	
	for (i = 1; i <= m; i++) {
		scanf ("%d %d %d", &x, &y, &c);
		G[y].push_back (x); C[x][y] = c;
	}
	
	memset (V, INF, sizeof (V));
	
	V[0][1] = 0;
	for (cfg = 0; cfg < (1 << n); cfg++)
		for (i = 0; i <= n; i++)
			if (cfg & (1 << i))
				for (it = G[i].begin (); it != G[i].end (); it++)
					if (cfg & (1 << (*it)))
						V[i][cfg] = min (V[i][cfg], V[*it][cfg ^ (1 << i)] + C[*it][i]);
	
	sol = INF;
	for (it = G[0].begin (); it != G[0].end (); it++)
		sol = min (sol, V[*it][(1 << n) - 1] + C[*it][0]);
	
	printf ("%d", sol);
	
	return 0;
}