#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.out");

	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;
}