#include <fstream>

using namespace std;

const int INF = 100000000;
const int MAXN = 20;

int N, M, Sol;
int P[MAXN], U[MAXN];
int C[MAXN][MAXN];

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

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

		Sol = min(Sol, res);

		return;
	}
	
	for (int 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 = INF;
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j) C[i][j] = INF;

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

	back(1);

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

	return 0;
}