#include <fstream>
#include <set>
#include <stack>

#define MAX_N		((unsigned int)18)
#define INFINITE	((unsigned int)-1)

class Pair
{
public:
	int node;
	int cost;

public:
	Pair(int _node, int _cost) : 
		node(_node), cost(_cost)
	{
	}

	bool operator < (const Pair &_other) const
	{
		return this->cost < _other.cost;
	}
};

typedef std::multiset<Pair>		Graf;
typedef std::stack<int>			Stack;

Stack solution;
int visited[MAX_N];
int N;
unsigned int sol = INFINITE;
Graf graf[MAX_N];

int dfs(int _source, int _node, unsigned int _cost)
{
	Graf::iterator	itPair;

	solution.push(_node);
	visited[_node] = 1;

	if (solution.size() == N + 1)
		return _cost;

	for (itPair = graf[_node].begin(); graf[_node].end() != itPair; ++ itPair)
	{
		if (!visited[itPair->node])
		{
			return dfs(_source, itPair->node, _cost + itPair->cost);
		}
		else if ((solution.size() == N) && (itPair->node == _source))
		{
			return dfs(_source, itPair->node, _cost + itPair->cost);
		}
	}

	return INFINITE;
}

int main()
{
	int M, x, y, c;

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

	fin>>N>>M;

	while(M--)
	{
		fin>>x>>y>>c;
		graf[x].insert(Pair(y, c));
	}

	sol = dfs(0, 0, 0);

	if (sol == INFINITE)
		fout<<"Nu exista solutie";
	else
		fout<<sol;

	fin.close();
	fout.close();

	return 0;
}