#include<stdio.h>

const int NMAX=19;
const long INFINIT=1 << 30;

long m_cost[NMAX][NMAX], m_sol[NMAX][NMAX],cost_min=INFINIT;

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

int main()
{
	FILE *in,*out;
	in=fopen ("hamilton.in", "r");
	out=fopen ("hamilton.out", "w");
	
	int noduri,muchii,i,j,aux;

	fscanf (in,"%d %d", &noduri, &muchii);
	
	for (i = 0; i <= noduri; i++)
		for (j = 0; j <= noduri; j++) 
			m_cost[i][j] = INFINIT;

	for (i = 0; i < (1 << noduri); i++)
		for (j = 0; j <= noduri; j++) 
			m_sol[i][j] = INFINIT;
	
	while (muchii --)
	{
		int x, y;
		long cost;
		
		fscanf (in,"%d %d %ld", &x, &y, &cost);
		
		m_cost[x][y] = cost;
	}
	
	m_sol[1][0] = 0;
	
	for (i = 0; i < (1 << noduri); i++)
		for (j = 0; j < noduri; j++)
		{
			if (! (i & (1 << j))) 
				continue;
			for (aux = 0; aux < noduri; aux++)
			{
				if (!(i & (1 << aux)) || (m_cost[aux][j] == INFINIT) || (aux == j) )
					continue;
				m_sol[i][j] = min(m_sol[i][j], m_sol[i - (1 << j)][aux] + m_cost[aux][j]);
				/*	for (i = 0; i < (1 << noduri); i++)
					{	
						printf("\n");
						for (j = 0; j < noduri; j++)				
							printf("%ld ",m_sol[i][j]);
					}

					printf("\n");*/
			}
		}
			
	for (i = 1; i < noduri; i++) 
		if (m_sol[(1 << noduri) - 1][i] != INFINIT) 
			cost_min = min(cost_min, m_sol[(1 << noduri) - 1][i] + m_cost[i][0]);
	
	if (cost_min == INFINIT) 
		fprintf (out,"Nu exista solutie.");
	else 
		fprintf (out,"%ld", cost_min);
	fclose(in);
	fclose(out);
	return 0;
}