#include <fstream>
#include <vector>

#define NMax 20

using namespace std;

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

int nodes, edges, n1, n2, c, mark[NMax], dmin = 1000000000;
vector<int> G[NMax], cost[NMax];

void dfs(int node, int touchedNodes, int mcost)
{
	mark[node] = true;

	for (vector<int>::iterator itg = G[node].begin(), itc = cost[node].begin(); itg != G[node].end(); itg++, itc++) {

		if (!mark[*itg])
			dfs(*itg, touchedNodes + 1, mcost + *itc);

		if (*itg == 0 && touchedNodes == nodes && mcost + *itc < dmin)
			dmin = mcost + *itc;

	}

	mark[node] = false;
}

int main()
{
	f >> nodes >> edges;

	for (int i = 1; i <= edges; i++) {
		f >> n1 >> n2 >> c;

		G[n1].push_back(n2);
		cost[n1].push_back(c);
	}

	dfs(0, 1, 0);
	if (dmin == 1000000000)
		g << "Nu exista solutie";
	else
		g << dmin;

	return 0;
}