#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

#define maxN 20
#define maxConf (1 << 19)
#define inf (1 << 30)

int Cost[maxN][maxN], DP[maxConf][maxN];

int main()
{
	freopen ("hamilton.in", "r", stdin);
	freopen ("hamilton.out", "w", stdout);
	
	int N, M;
	
	scanf ("%d %d", &N, &M);
	
	for (int i = 0; i <= N; ++ i)
		for (int j = 0; j <= N; ++ j) Cost[i][j] = inf;
	for (int conf = 0; conf <= (1 << N); ++ conf)
		for (int i = 0; i <= N; ++ i) DP[conf][i] = inf;
	DP[1][0] = 0;
	
	while (M --)
	{
		int x, y, c;
		
		scanf ("%d %d %d", &x, &y, &c);
		
		Cost[x][y] = c;
	}
	
	for (int conf = 0; conf < (1 << N); ++ conf)
		for (int i = 0; i < N; ++ i)
		{
			if (! (conf & (1 << i))) continue;
			
			for (int bit = 0; bit < N; ++ bit)
			{
				if (! (conf & (1 << bit))) continue;
				if (Cost[bit][i] == inf) continue;
				if (bit == i) continue;
				
				DP[conf][i] = min (DP[conf][i], DP[conf - (1 << i)][bit] + Cost[bit][i]);
			}
		}
	
	int sol = inf;
	
	for (int i = 1; i < N; ++ i)
		if (DP[(1 << N) - 1][i] != inf) sol = min (sol, DP[(1 << N) - 1][i] + Cost[i][0]);
	
	printf ("%d", sol);
	
	return 0;
}