#include <bits/stdc++.h>
#define INF 2e9
using namespace std;

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

int n, k, a[20][20], dp[1 << 20][20], N, sol;

int main()
{
	int i, j, x, y, cost, mask;
	fin >> n >> k;
	for (i = 1; i <= k; i++)
	{
		fin >> x >> y >> cost;
		a[x][y] = cost;
	}

	N = (1 << n);
	for (i = 0; i < N; i++)
		for (j = 0; j < n; j++)
			dp[i][j] = INF;

	dp[1][0] = 0;
	for (mask = 3; mask < N; mask += 2)
		for (i = 0; i < n; i++)
		if (mask & (1 << i))
		{
			x = mask - (1 << i);
			for (j = 0; j < n; j++)
				if (x & (1 << j) and a[j][i])
					dp[mask][i] = min(dp[mask][i], dp[x][j] + a[j][i]);
		}

	sol = INF;
	for (i = 1; i < n; i++)
		if (a[i][0])
			sol = min(sol, dp[N - 1][i] + a[i][0]);

	if (sol == INF)
		fout << "Nu exista solutie\n";
	else 
	fout << sol << "\n";

	return 0;
}