#include <iostream>
#include <fstream>
#include <vector>
#define INF 10000000
#define nmax 22

using namespace std;

const char iname[] = "hamilton.in";
const char oname[] = "hamilton.out";

ifstream fin(iname);
ofstream fout(oname);

int N, M, sol, i, x, y, j, k;
vector<int> A[nmax];
int dp[1 << nmax][nmax], C[nmax][nmax];

int main()
{	
	sol = INF;
	fin >> N >> M;
	for(i = 1; i <= M; i ++)
	{
		fin >> x >> y;
		A[y].push_back(x); //salvez in ordine inversa
		fin >> C[x][y]; //cost pe muchia x -> y
	}
	
	for(i = 0; i <= (1 << N) - 1; i ++)
		for(j = 0; j < N; j ++)
			dp[i][j] = INF;
	
	dp[1][0] = 0;
		
	for(i = 0; i <= (1 << N) - 1; i ++)
		for(j = 0; j < N; j ++)
			if(i & (1 << j))
				for(k = 0; k < A[j].size(); k ++)
					if(i & (1 << A[j][k]))
						dp[i][j] = min(dp[i][j], dp[i & ~(1 << j)][ A[j][k] ] + C[ A[j][k] ][j]);
					
			
	for(i = 0; i < A[0].size(); i ++)
		sol = min(sol, dp[(1 << N) - 1][A[0][i]] + C[A[0][i]][0]);
	
	if(sol == INF)
		fout << "Nu exista solutie";
	else
		fout << sol;
	return 0;
}