#include <cstdio>

const int MAX_SIZE(18);
const int MAX_CONF(1 << 18);
const int MAX_VALUE(1 << 30);

int cost [MAX_SIZE] [MAX_SIZE];
int conf [MAX_CONF] [MAX_SIZE];

struct list
{
	int vertex;
	struct list *next;
} *graph [MAX_SIZE];

int n, m, min_cost(MAX_VALUE);

inline void add (int x, int y)
{
	struct list *new_node(new struct list);
	new_node->vertex = y;
	new_node->next = graph[x];
	graph[x] = new_node;
}

inline void read (void)
{
	std::freopen("hamilton.in","r",stdin);
	std::scanf("%d %d",&n,&m);
	int i, j;
	for (i = 0 ; i < n ; ++i)
		for (j = 0 ; j <= n ; ++j)
			cost[i][j] = MAX_VALUE;
	for (int counter(0), x, y ; counter < m ; ++counter)
	{
		std::scanf("%d %d",&x,&y);
		std::scanf("%d",&cost[x][y]);
		add(y,x);
	}
	std::fclose(stdin);
}

inline void print (void)
{
	std::freopen("hamilton.out","w",stdout);
	if (min_cost == MAX_VALUE)
		std::printf("Nu exista solutie");
	else
		std::printf("%d",min_cost);
	std::putchar('\n');
	std::fclose(stdout);
}

inline int min (int a, int b)
{
	return (a < b ? a : b);
}

inline int bit (int x)
{
	return 1 << x;
}

inline void Hamilton (void)
{
	int i, j;
	struct list *iterator;
	const int END(bit(n));
	for (i = 1 ; i < END ; ++i)
		for (j = 0 ; j < n ; ++j)
			conf[i][j] = MAX_VALUE;
	conf[1][0] = 0;
	for (i = 1 ; i < END ; ++i)
		for (j = 0 ; bit(j) <= i ; ++j)
			if (i & bit(j))
				for (iterator = graph[j] ; iterator ; iterator = iterator->next)
					if (i & bit(iterator->vertex))
						conf[i][j] = min(conf[i][j],conf[i ^ bit(j)][iterator->vertex] + cost[iterator->vertex][j]);
	for (iterator = graph[0] ; iterator ; iterator = iterator->next)
		min_cost = min(min_cost,conf[END - 1][iterator->vertex] + cost[iterator->vertex][0]);
}

int main (void)
{
	read();
	Hamilton();
	print();
	return 0;
}