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

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

typedef vector < vector <edge> > graph;


void solve(const graph &G,int k,int conf,vector < vector<int> > & pd)
{
	queue< pair<int,int> > Q;
	//vector< vector <bool> > inQ(1 << G.size(),vector<bool>(G.size(),false));

	pd[1][0] = 0; //lantul hamiltonian de cost minim incluzand nodurile {0}
	Q.push( make_pair(1,0) );
	//inQ[1][0] = true;

	while(!Q.empty()) //bellman-ford extins la stari bidimensionale
	{
		int conf = Q.front().first, k = Q.front().second;
		Q.pop();
		//inQ[conf][k] = false;

		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;

					Q.push( make_pair(conf | 1 << G[k][i].to,G[k][i].to) );
					//inQ[conf | 1 << G[k][i].to][G[k][i].to] = true;
				}
			}
		}
	}
}

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

	solve(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;
}