#include<fstream>
#include<vector>
#include<cmath>
using namespace std;
int n,m,cost[20][20];
vector <int> G[20];
int mask[20],C[263000][20],sol=2000000000;

void Citire()
{
	int i,x,y,c;
	ifstream fin("hamilton.in");
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>x>>y>>c;
		cost[x][y]=c;
		G[x].push_back(y);
	}
	fin.close();
}

void Rezolvare()
{
	if(n==1)
	{
		sol=0;
		return;
	}
	int i,conf,lim;
	vector <int>::iterator it;
	for(i=0;i<n;i++)
		mask[i]=(1<<i);
	lim=(1<<n);
	for(conf=0;conf<lim;conf++)
		for(i=0;i<n;i++)
			C[conf][i]=2000000000;
	C[1][0]=0;
	for(conf=0;conf<lim;conf++)
	{
		for(i=0;i<n;i++)
		{
			if((conf&mask[i])!=0)
			{
				for(it=G[i].begin();it!=G[i].end();it++)
				{
					if((mask[*it]&conf)==0)
						C[conf|mask[*it]][*it]=min(C[conf|mask[*it]][*it],C[conf][i]+cost[i][*it]);
				}
			}
		}
	}
	conf=lim-1;
	for(i=1;i<n;i++)
	{
		if(cost[i][0]!=0)
			sol=min(sol,C[conf][i]+cost[i][0]);
	}
}

void Afisare()
{
	ofstream fout("hamilton.out");
	if(sol==2000000000)
		fout<<"Nu exista solutie\n";
	else
		fout<<sol<<"\n";
	fout.close();
}

int main()
{
	Citire();
	Rezolvare();
	Afisare();
	return 0;
}