#include <stdio.h>
#include <algorithm>
#include <vector>
#include <bitset>
using namespace std;

FILE *fi = fopen ("hamilton.in", "r");
FILE *fo = fopen ("hamilton.out", "w");

const int dim = 20, OO = 1<<30;
int N, M, R, X[dim];
struct nod { int v, c; };
vector <nod> L[dim];
bitset <dim> viz;

void cit ()
{
	nod v;
	fscanf (fi, "%d%d", &N, &M);
	for (int i = 0, x, y; i < M; i++)
	{
		fscanf (fi, "%d%d%d", &x, &v.v, &v.c);
		x++, v.v++;
		L[x].push_back (v);
	}
	X[0] = 1;
	viz[1] = 1;
	R = OO;
}

void back (int k, int cc)
{
	if (k == N + 1)
	{
		R = min (R, cc);
		return;
	}
	
	int n = X[k-1], f, c;
	for (int i = 0; i < L[n].size(); i++)
	{
		f = L[n][i].v;
		c = L[n][i].c;
		if ((viz[f] == 0 && k < N) || (f == 1 && k == N))
		{
			X[k] = f;
			viz[f] = 1;
			back (k + 1, cc + c);
			viz[f] = 0;
		}
	}
}

void afi ()
{
	if (R == OO)
		fprintf (fo, "Nu exista solutie");
	else
		fprintf (fo , "%d\n", R);
}

int main ()
{
	cit ();
	back (1, 0);
	afi ();
	
	return 0;
}