#include<fstream>
#include<vector>
#define pb push_back
#define mp make_pair
#define oo (1<<30)
#define nmax 18
using namespace std;
vector< pair <int,int> > v[nmax];
int c[1<<nmax][nmax];
int calc(int conf, int nod)
{
	if(c[conf][nod]!=-1)
		return c[conf][nod];
	c[conf][nod]=oo;
	vector< pair <int,int> >:: iterator fiu;
	for(fiu=v[nod].begin();fiu!=v[nod].end();fiu++)
		if(conf&(1<<(*fiu).first)&&((*fiu).first||conf==1+(1<<nod)))
		{
			int value=calc(conf^(1<<nod),(*fiu).first);
			if(c[conf][nod]>value+(*fiu).second)
				c[conf][nod]=value+(*fiu).second;
		}
	return c[conf][nod];
}
int main()
{
	int n,m,x,y,cost,N,i,j;
	ifstream fin("hamilton.in");
	ofstream fout("hamilton.out");
	fin>>n>>m;
	while(m--)
	{
		fin>>x>>y>>cost;
		v[y].pb(mp(x,cost));
	}
	N=(1<<n);
	for(i=0;i<N;i++)
		for(j=0;j<n;j++)
			c[i][j]=-1;
	c[1][0]=0;
	int sol=oo,value;
	vector< pair <int,int> >:: iterator fiu;
	for(fiu=v[0].begin();fiu!=v[0].end();fiu++)
	{
		value=calc(N-1,(*fiu).first);
		if(sol>value+(*fiu).second)
			sol=value+(*fiu).second;
	}
	if(sol!=oo)
		fout<<sol;
	else
		fout<<"Nu exista solutie";			
	return 0;
}