#include <cstdio>
#include <vector>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

#define PB push_back
#define MKP make_pair
#define INF 0x3f3f3f3f

int N , M , costuri[20][20] , minim;
bool viz[20];

vector <pair <int , int> > lista[20];


void dfs (int nod , int pas , int cost)
{
	viz[nod] = true;
	
	for (unsigned int i = 0 ; i < lista[nod].size () ; ++i)
	{
		int nodcur = lista[nod][i].first;
		
		if (!viz[nodcur])
			dfs (nodcur , pas + 1 , cost + costuri[nod][nodcur]);
		
		if (pas == N && nodcur == 0)
			minim = min (minim , cost + costuri[nod][nodcur]);
	}
	
	viz[nod] = false;
	
}


int main ()
{
	freopen ("hamilton.in" , "r" , stdin);
	freopen ("hamilton.out" , "w" , stdout);
	
	scanf ("%d %d" , &N , &M);
	
	
	int a , b , c;
	
	for (int i = 1 ; i <= M ; ++i)
	{
		scanf ("%d %d %d" , &a , &b , &c);
		
		lista[a].PB (MKP (b , c));
		costuri[a][b] = c;
	}
	
	
	minim = INF;
	
	
	dfs (0 , 1 , 0);
	
	
	if (minim == INF)
		printf ("Nu exista solutie");
	
	else printf ("%d" , minim);
	
	
	return 0;
}