#include <fstream>
#include <vector>
#include <cstring>
#define INF 0x3f3f3f3f
using namespace std;
int n,p[19],c[18][18],dp[1<<18][18];
vector<int> g[18];
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
int main()
{
	int m,i,j,k,lim,conf;
	memset(dp,INF,sizeof dp);
	p[0]=1;
	fin>>n>>m;
	for(i=0;i<n;++i)
	{
		p[i+1]=p[i]<<1;
		dp[p[i]][i]=0;
	}
	while(m--)
	{
		fin>>i>>j>>k;
		g[j].push_back(i);
		c[i][j]=k;
	}
	lim=p[n]-1;
	for(conf=1;conf<=lim;++conf)
		for(i=0;i<n;++i)
			if(p[i]&conf && dp[conf][i])
				for(j=0;j<g[i].size();++j)
				{
					k=g[i][j];
					dp[conf][i]=min(dp[conf][i],dp[conf^p[i]][k]+c[k][i]);
				}
	m=INF;
	for(i=0;i<g[0].size();++i)
	{
		j=g[0][i];
		m=min(m,dp[lim][j]+c[j][0]);
	}
	if(m<INF)
		fout<<m<<"\n";
	else
		fout<<"Nu exista solutie\n";
	return 0;
}