#include <fstream>

using namespace std;

const int INF = 1e9;

int n, m, cost[20][20], dp[20][1 << 20];
// dp[i][mask] = costul minim de la 0 la i prin drumul mask

void Hamilton()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < (1 << n); j++)
		{
			dp[i][j] = INF;
		}
	}
	dp[0][1] = 0;
}

int main()
{
	ifstream fin("hamilton.in");
	ofstream fout("hamilton.out");
	fin >> n >> m;
	int x, y, c;
	while (m--)
	{
		fin >> x >> y >> c;
		cost[x][y] = c;
	}
	Hamilton();
	for (int mask = 0; mask < (1 << n); mask++)
	{
		for (int i = 0; i < n; i++)
		{
			if(dp[i][mask] == INF){
				continue;
			}
			for(int vec = 0; vec < n; vec++){
				if(!(mask & (1 << vec)) && cost[i][vec]){
					dp[vec][mask + (1 << vec)] = min(dp[vec][mask + (1 << vec)],
													dp[i][mask] + cost[i][vec]);
				}
			}
		}
	}
	int sol = INF;
	for (int i = 0; i < n; i++)
	{
		if (cost[i][0])
		{
			sol = min(sol, dp[i][(1 << n) - 1] + cost[i][0]);
		}
	}
	if (sol == INF)
	{
		fout << "Nu exista solutie";
	}
	else
	{
		fout << sol;
	}
	return 0;
}