#include "stdio.h"

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

int m_cost[NMAX][NMAX], m_sol[MAX][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;
	
	for (i=1;i<=muchii;i++)
	{
		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))) 
				for (aux = 0; aux < noduri; aux++)
					if ((i & (1 << aux)) && (m_cost[aux][j] != INFINIT) && (aux != j) )
						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;
}