#include <fstream>
#include <vector>
using namespace std;

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

const int oo = 2e9;
int n, m, cost[18][18], dp[1<<18][18];
vector<int> g[18];

void read()
{
	in >> n >> m;
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < n; ++j)
			cost[i][j] = oo;
	int x, y;
	while(m--)
	{
		in >> x >> y;
		g[y].push_back(x);
		in >> cost[x][y];
	}
}

void solve()
{
	for(int i = 0; i < (1<<n); ++i)
		for(int j = 0; j < n; ++j)
			dp[i][j] = oo;
	dp[1][0] = 0;
	for(int i = 0; i < (1<<n); ++i)
		for(int j = 0; j < n; ++j)
			if(i & (1<<j))
				for(auto k : g[j])
					if(i & (1<<k))
						dp[i][j] = min(dp[i][j], dp[i ^ (1<<j)][k] + cost[k][j]);
}

void afis()
{
	int sol = oo;
	for(auto i : g[0])
		sol = min(sol, dp[(1<<n) - 1][i] + cost[i][0]);
	if(sol == oo) out << "Nu exista solutie";
	else out << sol;
}

int main()
{
	read();
	solve();
	afis();
	return 0;
}