#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];
vector< pair <int,int> >:: iterator fiu;
int c[1<<nmax][nmax];
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]=oo;
	c[1][0]=0;
	for(i=0;i<N;i++)
		for(j=0;j<n;j++)
			if(i&(1<<j))
				for(fiu=v[j].begin();fiu!=v[j].end();fiu++)
					if(i&&(1<<(*fiu).first))
						if(c[i][j]>c[i^(1<<j)][(*fiu).first]+(*fiu).second)
							c[i][j]=c[i^(1<<j)][(*fiu).first]+(*fiu).second;
	int sol=oo;
	for(fiu=v[0].begin();fiu!=v[0].end();fiu++)
		if(sol>c[N-1][(*fiu).first]+(*fiu).second)
			sol=c[N-1][(*fiu).first]+(*fiu).second;
	if(sol!=oo)
		fout<<sol;
	else
		fout<<"Nu exista solutie";			
	return 0;
}