#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <utility>
using namespace std;

#define NMAX 20
#define KMAX (1 << NMAX)
#define INF 20000000

int n, m;
int i, j, k, c;
int result;
int d[KMAX][NMAX];
vector<pair<int, int> > g[NMAX];

int main()
{
	freopen("hamilton.in", "r", stdin);
	freopen("hamilton.out", "w", stdout);

	scanf("%d %d", &n, &m);

	for (k = 0; k < m; ++k)
	{
		scanf("%d %d %d", &i, &j, &c);
		g[i].push_back(pair<int, int>(j, c));
	}

	k = (1 << n);
	for (i = 0; i < n; i++)
		for (j = 0; j < k; j++)
			d[j][i] = INF;

	d[1][0] = 0;
	for (j = 1; j < k; ++j)
		for (i = 0; i < n; ++i)
			if (j & (1 << i))
				for (vector<pair<int, int> >::iterator it = g[i].begin(); it != g[i].end(); ++it)
					if (j & (1 << (*it).first))
						if (d[j][i] > d[j ^ (1<< i)][(*it).first] + (*it).second)
							d[j][i] = d[j ^ (1<< i)][(*it).first] + (*it).second;

	result = INF;
	for (vector<pair<int, int> >::iterator it = g[0].begin(); it != g[0].end(); ++it)
		if (result > d[k-1][(*it).first] + (*it).second)
			result = d[k-1][(*it).first] + (*it).second;

	printf("%d\n", result);

	return 0;
}