#include <iostream>
#include <fstream>
#include <vector>
#include <string.h>

const static int NMAX = 19;
const static int INFINIT = 100000000;

using namespace std;

ifstream input("hamilton.in");
ofstream output("hamilton.out");

vector <int> graph[NMAX];
int D[1 << NMAX][NMAX] , nr_noduri , nr_muchii;
int costuri[NMAX][NMAX];

int main(int argc, char **argv) 
{
	input >> nr_noduri >> nr_muchii;
	int x , y , c;
	
	for (int i = 0;i<nr_noduri;i++)
		for (int j = 0;j<nr_noduri;j++)
			costuri[i][j] = INFINIT;
	
	for (int i = 0;i<nr_muchii;i++)
	{
		input >> x >> y >> c;
		graph[y].push_back(x);
		costuri[x][y] = c;
	}
	
	for (int i = 0;i<(1 << nr_noduri);i++)
		for (int j = 0;j<nr_noduri;j++)
			D[i][j] = INFINIT;
		
	D[1][0] = 0;
			
	
	for (int i = 0;i<(1 << nr_noduri);i++)
		for (int j = 0;j<nr_noduri;j++)
			if (i & (1 << j))
				for (int k = 0;k<graph[j].size();k++)
					if (i & (1 << graph[j][k]))
						D[i][j] = min(D[i][j] , D[i ^ (1 << j)][graph[j][k]] + costuri[graph[j][k]][j]);
					
	int solutie = INFINIT;
	for (int i = 0;i<graph[0].size();i++)
		solutie = min(solutie , D[(1 << nr_noduri) - 1][graph[0][i]] + costuri[graph[0][i]][i]);
	
	if (solutie == INFINIT) 
	{
		output << "Nu exista solutie\n";
	}
	else
	{
		output << solutie;
	}
	
	input.close();
	output.close();
	
    return 0;
}