#include <fstream>
#include <vector>

using namespace std;

const char InFile[]="hamilton.in";
const char OutFile[]="hamilton.out";
const int MaxN=18;
const int INF=1<<30;

ifstream fin(InFile);
ofstream fout(OutFile);

int N,M,x,y,cost,Cost[MaxN][MaxN],C[1<<MaxN][MaxN];
vector<int> G[MaxN];

int main()
{
	fin>>N>>M;
	for(register int i=0;i<N;++i)
	{
		for(register int j=0;j<N;++j)
		{
			Cost[i][j]=INF;
		}
	}
	for(register int i=0;i<M;++i)
	{
		fin>>x>>y;
		G[y].push_back(x);
		fin>>Cost[x][y];
	}
	fin.close();

	int maxConf=1<<N;
	for(int conf=0;conf<maxConf;++conf)
	{
		for(int j=0;j<N;++j)
		{
			C[conf][j]=INF;
		}
	}
	C[1][0]=0;

	for(int conf=0;conf<maxConf;++conf)
	{
		for(int j=0;j<N;++j)
		{
			if(conf&(1<<j))
			{
				for(vector<int>::iterator it=G[j].begin();it!=G[j].end();++it)
				{
					if(conf&(1<<(*it)))
					{
						C[conf][j]=min(C[conf][j],C[conf^(1<<(j))][*it]+Cost[*it][j]);
					}
				}
			}
		}
	}

	--maxConf;
	int sol=INF;
	for(vector<int>::iterator it=G[0].begin();it!=G[0].end();++it)
	{
		sol=min(sol,C[maxConf][*it]+Cost[*it][0]);
	}

	if(sol==INF)
	{
		fout<<"Nu exista solutie\n";
	}
	else
	{
		fout<<sol;
	}
	fout.close();
	return 0;
}