#include <stdio.h>
#include <stdlib.h>
#define MAXN 18
#define MAX (1<<20)

FILE *fin, *fout;
int N, M;
int A[MAXN][MAXN], B[MAXN][MAXN];
int sol = MAX;

int max (int a, int b)
{
	if (a>b)
		return a;
	else
		return b;
}

void init ()
{
	int i,j;
	for (i=0; i<M; i++)
		for (j=0; j<M; j++)
			A[i][j] = MAX;
}

void citeste ()
{
	int i;
	int x,y,z;
	for (i=0; i<M; i++)
	{
		fscanf (fin, "%d", &x);
		fscanf (fin, "%d", &y);
		fscanf (fin, "%d", &z);
		A[x][y] = z;
	}
}

void parcurge ()
{
	int i,j,k;
	for (i=0; i<(1<<N); i++)
		for (j=0; j<N; j++)
			if (i & (1<<j))
				for (k=0; k<N; k++)
					if ((i & (1<<k)) && (A[k][j] != MAX) && (k != j))
						B[i][j] = max (B[i][j], B[i-(1<<j)][k] + A[k][j]);
}

void rezultat ()
{
	int i;
	for (i=0; i<N; i++)
		if (B[(1 << N) - 1][i] != MAX)
			sol = max (sol, B[(1 << N) - 1][i] + A[i][0]);
	if (sol == MAX)
		fprintf (fout, "Nu Exista.");
	else
		fprintf (fout, "%d", sol-MAX+1);
}

int main () 
{
	fin = fopen ("hamilton.in", "r");
	fout = fopen ("hamilton.out", "w");
	if (!fin || !fout)
	{
		fprintf (fout,"Eroare");
		return 0;
	}
	fscanf (fin, "%d", &N);
	fscanf (fin, "%d", &M);
	init();
	citeste();
	parcurge();
	rezultat();
	fclose (fin);
	fclose (fout);
	return 0;
}