#include <cstdio>

using namespace std;

class LinkedList
{
	public:
	int info;
	LinkedList * next;

	LinkedList(int info)
	{
		this->info = info;
		next = NULL;
	}

	LinkedList()
	{
		this->info = -1;
		next = NULL;
	}

	void addNext(int info)
	{
		if(next == NULL)
			next = new LinkedList(info);
		else
			next->addNext(info);
	}

	LinkedList* getNext()
	{
		return next;
	}

	int listSize()
	{
		if(next != NULL)
			return 1 + next -> listSize();
		return 1;
	}
};


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

int muchii[20][20];
int cost[262150][20];
LinkedList* A[20];


int main()
{
	freopen("hamilton.in", "r", stdin);
	freopen("hamilton.out", "w", stdout);

	int n, m, i, j;
	LinkedList * x = NULL;

	scanf("%d%d", &n, &m);

	for(i=0; i<n; ++i)
		for(j=0; j<n; ++j)
			muchii[i][j] = 100000000;

	for(i=0; i<(1<<n); ++i)
		for(j=0;j<n; ++j)
			cost[i][j] = 100000000;

	cost[1][0]=0;

	for(i=1; i<=m; ++i)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		if(A[y]==NULL)
		{
			A[y] = new LinkedList(x);
		}
		else
			A[y]->addNext(x);
		scanf("%d", &muchii[x][y]);
	}

	for(i=0; i<(1<<n); ++i)
		for(j=0; j<n; ++j)
			if(i & (1<<j))
			{
				x = A[j];
				while(x!=NULL)
				{
					if(i & (1<< (x->info)))
						cost[i][j] = min(cost[i][j], cost[i ^ (1<<j)][x->info] + muchii[x->info][j]);
					x = x->getNext();
				}
			}

	int sol = 100000000;
	x = A[0];
	while(x!=NULL)
	{
		sol = min(sol, cost[(1<<n)-1][x->info] + muchii[x->info][0]);
		x = x->getNext();
	}

	if(sol == 100000000)
		printf("Nu exista solutie\n");
	else
		printf("%d\n", sol);

	return 0;
}