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

struct edge
{
	int to,cost;
	edge(int _to, int _cost) : to(_to), cost(_cost) {}
};

typedef vector < vector <edge> > graph;


void solve_r(const graph &G,int k,int conf,vector < vector<int> > & pd)
{
	for(int i = 0; i < G[k].size(); ++i)
	{
		if( (1 << G[k][i].to & conf) == 0 ) //daca nodul nu exista deja in configuratie
		{
			if(pd[conf | 1 << G[k][i].to][G[k][i].to] > pd[conf][k] + G[k][i].cost)
			{
				pd[conf | 1 << G[k][i].to][G[k][i].to] = pd[conf][k] + G[k][i].cost;
				solve_r(G,G[k][i].to,conf | 1 << G[k][i].to,pd);
			}
		}
	}
}

int solve(const graph &G,const graph &Gt)
{
	vector< vector <int> > pd(1 << G.size(),vector<int>(G.size(),INT_MAX));

	pd[1][0] = 0; //lantul hamiltonian de cost minim incluzand nodurile {0}

	solve_r(G,0,1,pd);

	int min = INT_MAX;
	for(int i = 0; i < Gt[0].size(); ++i)
	{
		if( pd[ (1 << G.size()) - 1 ][Gt[0][i].to] != INT_MAX)
			if(min > pd[ (1 << G.size()) - 1 ][Gt[0][i].to] + Gt[0][i].cost)
				min = pd[ (1 << G.size()) - 1 ][Gt[0][i].to] + Gt[0][i].cost;
	}

	return min;
}

int main()
{
	ifstream fin("hamilton.in",ifstream::in);
	ofstream fout("hamilton.out",ofstream::out);

	int V,E;
	fin >> V >> E;

	graph G(V),Gt(V);

	while(E--)
	{
		int from,to,cost;
		fin >> from >> to >> cost;
		G[from].push_back(edge(to,cost));
		Gt[to].push_back(edge(from,cost));
	}
	int sol = solve(G,Gt);
	if(sol == INT_MAX)
	{
		fout << "Nu exista solutie";
	}
	else fout << sol;

	return 0;
}