#include <iostream>
#include <fstream>
#define inf 2000000000

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n, m, dp[(1<<18)+10][18], nod[20][20];

int main()
{
	fin >> n >> m;
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			nod[i][j] = -1;
	for(int mask=0; mask<(1<<n); mask++)
		for(int bit=0; bit<n; bit++)
			dp[mask][bit] = inf;
	dp[1][0] = 0;

	for(int i=1; i<=m; i++)
		{	int nod1, nod2, cost;
			fin >> nod1 >> nod2 >> cost;
			nod[nod1][nod2] = cost;
		}
	for(int mask=2; mask<(1<<n); mask++)
		for(int i=0; i<n; i++)
			if(mask & (1 << i))
				for(int j=0; j<n; j++)
					if(i != j && mask & (1 << j) && nod[j][i] != -1)
						dp[mask][i] = min(dp[mask][i], dp[mask^(1<<i)][j] + nod[j][i]);
	int ans = inf;
	for(int i=1; i<n; i++)
		if(nod[i][0] != -1)
			ans = min(ans, dp[(1<<n)-1][i] + nod[i][0]);
	if(ans == inf)
		fout << "Nu exista solutie" << '\n';
	else
		fout << ans << '\n';
	return 0;
}