#include <bits/stdc++.h>

using namespace std;

const long long r = 1001;
const long long q = 262150;
const long long s = 100000000;

long long N, M, Sol;
long long Cost[r][r];
long long C[q][r];
vector <long long> A[r];

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

	fin >> N >> M;

	for (long long i = 0; i < N; ++i)
		for (long long j = 0; j < N; ++j) Cost[i][j] = s;

	for (long long i = 1; i <= M; ++i)
	{
		long long x, y;

		fin >> x >> y;
		A[y].push_back(x);
		fin >> Cost[x][y];
	}

	for (long long i = 0; i < 1 << N; ++i)
		for (long long j = 0; j < N; ++j) C[i][j] = s;

	C[1][0] = 0;

	for (long long i = 0; i < 1 << N; ++i)
		for (long long j = 0; j < N; ++j)
			if (i & (1<<j))
				for (size_t k = 0; k < A[j].size(); ++k)
					if (i & (1<<A[j][k]))
						C[i][j] = min(C[i][j], C[i ^ (1<<j)][ A[j][k] ] + Cost[ A[j][k] ][j]);

	Sol = s;
	for (size_t i = 0; i < A[0].size(); ++i)
		Sol = min(Sol, C[(1<<N) - 1][ A[0][i] ] + Cost[ A[0][i] ][0]);

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

	return 0;
}