#define MAX_N 18
#define INF 0x3f3f3f3f

#include <fstream>
#include <utility>
#include <bitset>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

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

int n, m, r = INF;
vector<pair<int, int>> G[MAX_N + 1];

bitset<1 << MAX_N> C[MAX_N + 1];

// Vizitat.
bitset<MAX_N + 1> V; 

void Df(int nod, int masca);
void CicluHam(int nod, int cost, int masca);
int NumaraBiti(int x);

int main()
{
	fin >> n >> m;
	for (int i = 0, x, y, c; i < m; ++i)
	{
		fin >> x >> y >> c;
		// Indexarea nodurilor incepe de la zero.
		++x;
		++y;
		G[x].emplace_back(c, y);
	}
	
	for (int masca = 0; masca < (1 << n); ++masca)
	{
		if (NumaraBiti(masca) == n) { break; }
		
		for (int nod = 1; nod <= n; ++nod)
		{
			if (!(masca & (1 << (nod - 1))))
			{
				V.reset();
				Df(nod, masca);
				C[nod][masca] = (n - NumaraBiti(masca)) == (int) V.count();
			}
		}
	}
	
	if (C[1][0])
	{
		CicluHam(1, 0, 0);
		
		if (r == INF)
		{
			fout << "Nu exista solutie";
		}
		else
		{
			fout << r;
		}
	}
	else
	{
		fout << "Nu exista solutie";
	}
	
	fin.close();
	fout.close();
	return 0;
}

void Df(int nod, int masca)
{
	V[nod] = true;
	for (const auto& vecin : G[nod])
	{
		if (!V[vecin.second] && (!(masca & (1 << (vecin.second - 1)))))
		{
			Df(vecin.second, masca);
		}
	}
}

void CicluHam(int nod, int cost, int masca)
{
	if (NumaraBiti(masca) == (n - 1))
	{
		for (const auto& vecin : G[nod])
		{
			if (vecin.second == 1)
			{
				r = min(r, cost + vecin.first);
				break;
			}
		}
	}
	else
	{
		for (const auto& vecin : G[nod])
		{
			if (C[vecin.second][masca] && !(masca & (1 << (vecin.second - 1))))
			{
				masca |= 1 << (nod - 1);
				CicluHam(vecin.second, cost + vecin.first, masca);
			}
		}
	}
}

int NumaraBiti(int x)
{
	int rasp = 0;
	for (int p = 0; p < 32; ++p)
	{
		if (x & (1 << p)) { ++rasp; }		
	}
	return rasp;
}