#include <stdio.h>
#include <string.h>
#include <vector>

#define nmax 18
#define pmax (1<<18)
#define nod first
#define cost second
#define inf 0x3f3f3f3f 

using namespace std;

typedef pair <int, int> ii;

int n, m, c [pmax+5] [nmax+5];
vector <ii> g [nmax];

void scan ()
{
	int a, b, c, i;
	scanf ("%d%d", &n, &m);
	for (i=1; i <= m; ++i)
	{
		scanf ("%d%d%d", &a, &b, &c);
		g [b].push_back (ii (a, c)); //muchii inverse!
	}
}

void init ()
{
	int i, j;
	for (i=0; i < (1<<n); ++i)
		for (j=0; j < n; ++j)
			c [i] [j]=inf;
       c [1] [0]=0;	
}

inline int min (int a, int b)
{
	if (a < b) return a;
	return b;
}

void lant ()
{
	int i, j, k, p=1<<n;
	for (i=0; i < p; ++i)
		for (j=0; j < n; ++j)
			if (i & (1 << j))
				for (k=0; k < g [j].size (); ++k)
					if (i & (1 << g [j] [k].nod))
						c [i] [j]=min (c [i] [j], c [i ^ (1<<j)] [g [j] [k].nod]+g [j] [k].cost);
}

int ciclu ()
{
	int i, m=inf, p=(1<<n)-1;
	for (i=0; i < g [0].size (); ++i)
		m=min (m, c [p] [g [0] [i].nod]+g [0] [i].cost);
	return m;
}

int main ()
{
	freopen ("hamilton.in", "r", stdin);
	freopen ("hamilton.out", "w", stdout);
	scan ();
	init ();
	lant ();
	printf ("%d\n", ciclu ());
	return 0;
}