#include <cstdio>
#include <string>
#include <algorithm>

#define N 18

using namespace std;

struct nod
{
	int x, c;
	nod *n;
};

nod * a[N];
int xx[N+1][N+1];
int cost[N+1][N+1];

inline void add(int i, int j, int c)
{
	nod * p = new nod;
	p->x = j;
	p->c = c;
	p->n = a[i];
	a[i] = p;
}

int n, m;
int dp[(1<<N) + 1][N+1];

void read()
{
	freopen("hamilton.in","r",stdin);
	scanf("%d %d\n", &n, &m);
	int p, q, c;
	while(m--)
	{
		scanf("%d %d %d\n", &p, &q, &c);
		++p; ++q;
		add(q, p, c);
		xx[p][q] = 1;
		cost[p][q] = c;
	}
	
}


void solve()
{
	int i, j;
	nod * k;

	memset(dp, 0x3f3f3f3f, sizeof(dp));
	
	dp[1][1] = 0;
	
	for(i = 2; i < (1<<n); ++i)	
		for(j = 1; j <= n; ++j)
			if(i & (1 <<(j-1)))
				for(k = a[j]; k ; k = k->n)
					if(i & (1 << (k->x-1)))
						dp[i][j] = min(dp[i][j],dp[i ^ (1<<(j-1))][k->x] + k->c);
	
	/*
	for(j = 1; j <= n; ++j)
		printf("%d ", dp[2][j]);
	printf("\n\n");
	*/
	int sol = 0x3f3f3f3f;
	
	for(int k = 2; k <= n; ++k)
		if(xx[k][1])
	{	
		sol = min(sol,dp[(1<<n) - 1][k] + cost[k][1]); 
	//	printf("%d ", dp[(1<<n) - 1][k]);
	}

	fprintf(stderr,"%d\n", sol);
	freopen("hamilton.out","w",stdout);
	printf("%d\n", sol);
}

int main()
{
	read();
	solve();
	return 0;
}