#include <fstream>

using namespace std;

const long long r = 100000000000;
const long long q = 1001;

long long N, M, Sol;
long long P[q], U[q];
long long C[q][q];

void back(long long k)
{
	if (k > N)
	{
		long long res = C[P[N]][P[1]];

		for (long long i = 1; i < N; ++i)
			res += C[P[i]][P[i+1]];

		Sol = min(Sol, res);

		return;
	}

	for (long long i = 0; i < N; ++i)
		if (!U[i])
		{
			U[i] = 1;
			P[k] = i;
			back(k+1);
			U[i] = 0;
		}
}

int main()
{
	ifstream fin("hamilton.in");
	ofstream fout("hamilton.out");

	fin >> N >> M;

	Sol = r;
	for (long long i = 0; i < N; ++i)
		for (long long j = 0; j < N; ++j) C[i][j] = r;

	for (long long i = 1; i <= M; ++i)
	{
		long long x, y;
		fin >> x >> y;
		fin >> C[x][y];
	}

	back(1);

	if (Sol == r) fout << "Nu exista solutie" << endl;
	else fout << Sol << endl;

	return 0;
}