#include <fstream>
#include <cstring>
using namespace std;

const int Nmax = 18;
const int inf = 0x3f3f3f3f;

int N,M;
int cost[Nmax+1][Nmax+1];
int C[1<<19][Nmax+1];

int solve(int mask,int node)
{
	if (C[mask][node] == -1)
	{
		C[mask][node] = inf;
		for (int i = 0; i < N; i++)
		{
			if (cost[i][node] > 0 && mask&(1<<i))
			{
				if (i == 0 && mask != (1<<node)+1) continue;
				C[mask][node] = min(C[mask][node],solve(mask^(1<<node),i)+cost[i][node]);
			}
		}	
	}	

	return C[mask][node];
}

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

	fin >> N >> M;
	for (int i = 1; i <= M; i++)
	{
		int a,b,c;
		fin >> a >> b >> c;
		cost[a][b] = c;
	}

    memset(C,-1,sizeof C);  
    C[1][0] = 0;
                           
    int bestPath = inf;      
    for (int i = 1; i < N; i++)
    	if (cost[i][0] > 0)
    		bestPath = min(bestPath,solve((1<<N)-1,i)+cost[i][0]);	

    if (bestPath == inf)
    	fout << "Nu exista solutie";
    else 
    	fout << bestPath << "\n";
}