#include<iostream>
#include<fstream>
#include<vector>
#include<string.h>
using namespace std;
#define bit( x , nr ) (  ( (x) & ( 1 << (nr) ) ) != 0)
const int NMAX = 19;
const int INF = 1<<30;
int a[NMAX][NMAX],d[NMAX][(1<<(NMAX-1))+1],n;
vector <int> v[NMAX];
int calc(int i, int s)
{
	int j;
	if((1<<i)==s)
		d[i][s]=0;
	else if(d[i][s]==-1) {
		d[i][s]=INF;
		for(j=0;j<=v[i].size()-1;j++)
			if(bit(s,v[i][j])) {
				if( v[i][j]==0 && s!=(1<<i)+1 )
					continue ;
				d[i][s]=min(d[i][s],calc(v[i][j],s-(1<<i))+a[v[i][j]][i]);
			}
	}
	return d[i][s];
}
int main ()
{
	int i,m,x,y,costmin;
	ifstream f("hamilton.in");
	ofstream g("hamilton.out");
	f>>n>>m;
	for(i=1;i<=m;i++) {
		f>>x>>y;
		v[y].push_back(x);
		f>>a[x][y];
	}
	f.close();
	memset(d,-1,sizeof(d));
	costmin=INF;
	for(i=0;i<=v[0].size()-1;i++)
		costmin=min(costmin,calc(v[0][i],(1<<n)-1)+a[v[0][i]][0]);
	if(costmin==INF)
		g<<"Nu exista solutie\n";
	else g<<costmin;
	g.close();
	return 0;
}