#include "stdio.h"

#define NMAX 20
#define INFINIT (1<<30)

int m_cost[NMAX][NMAX], m_sol[1<<NMAX][NMAX];

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

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

	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, cost;
		fscanf(in,"%d %d %d", &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 < 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,"%d", cost_min);
	fclose(in);
	fclose(out);
	return 0;
}