#include<iostream>
#include<fstream>
#include<string.h>
using namespace std;
#define bit( x , nr ) (  ( (x) & ( 1 << (nr) ) ) != 0)
const int NMAX = 18;
const int INF = 1<<30;
int a[NMAX][NMAX],d[NMAX][1<<NMAX],n;
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<=n-1;j++)
			if( bit(s,j) && i!=j && a[j][i] )
				d[i][s]=min(d[i][s],calc(j,s-(1<<i))+a[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;
		f>>a[x][y];
	}
	f.close();
	memset(d,-1,sizeof(d));
	costmin=INF;
	for(i=1;i<=n;i++)
		costmin=min(costmin,calc(i-1,(1<<n)-1));
	if(costmin==INF)
		g<<"Nu exista solutie\n";
	else g<<costmin;
	g.close();
	return 0;
}