#include<stdio.h>
#include<stdlib.h>

int A[19][19], B[(1<<19)][19];

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

int main()
{
	FILE *fin;
	fin = fopen ("hamilton.in","r");
	int i, j, k, n, m, x, y, z, sol, inf=(1<<30);
	fscanf (fin, "%d%d", &n, &m);
	for(i=0; i<n; i++)
		for(j=0; j<n; j++)
			A[i][j] = inf; 
	for (i=0; i<m; i++)
	{
		fscanf (fin, "%d%d%d", &x, &y, &z);
		A[x][y] = z;
	}
	for (i=0; i<n; i++)
		for (j=0; j<(1<<n); j++)
			B[j][i] = inf;
	B[1][0] = 0;
	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))
						if (A[k][j]!=inf && k!=j)
							B[i][j] = min(B[i][j], B[i-(1<<j)][k]+A[k][j]); 
	sol = inf;
	for (i=0; i<n; i++)
		if (B[(1<<n)-1][i] != inf)
			sol = min (sol, B[(1<<n)-1][i]+A[i][0]);
	fclose (fin);
	FILE *fout;
	fout = fopen ("hamilton.out", "w");
	if (sol!=inf)
		fprintf (fout, "%d", sol);
	else 
		fprintf (fout, "Nu exista solutie");
	fclose (fout);            
	return 0;
}