#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)
{
	pd[1][0] = 0; //lantul hamiltonian de cost minim incluzand nodurile {0}

	for(int conf = 0;conf < 1 << G.size() ; ++conf)
	{
		for(int k = 0; k < G.size(); ++k)
		{
			for(int i = 0; i < G[k].size(); ++i) // (k,i) itereaza toate muchiile grafului G
			{
				if( pd[conf][k] < INT_MAX && (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;
					}
				}
			}
		}
	}
}

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