#include <fstream>
#include <vector>
 
using namespace std;
 
const int MAXN = 20;
const int INF = 1000000000;
 
int N, M, Sol;
vector <int> A[MAXN], C[MAXN];
int U[MAXN];
 
void DFS(int nod, int nr, int cost)
{
	U[nod] = 1;
 
	for (size_t i = 0; i < A[nod].size(); ++i)
	{
		if (!U[A[nod][i]]) DFS(A[nod][i], nr+1, cost+C[nod][i]);
 
		if (nr == N && A[nod][i] == 0) Sol = min(Sol, cost+C[nod][i]);
	}
 
	U[nod] = 0;
}
 
int main()
{
	ifstream fin("hamilton.in");
	ofstream fout("hamilton.ok");
 
	Sol = INF;
 
	fin >> N >> M;
 
	for (int i = 1; i <= M; ++i)
	{
		int x, y, c;
 
		fin >> x >> y >> c;
		A[x].push_back(y);
		C[x].push_back(c);
	}
 
	DFS(0, 1, 0);
 
	if (Sol == INF) fout << "Nu exista solutie" << endl;
	else fout << Sol << endl;
 
	return 0;
}