#include<fstream>
#include<vector>
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");
const int MAXN=20;
const int MAXX=262150;
const int INF=0x3f3f3f;

int c[MAXX][MAXN];
int cost[MAXN][MAXN];
vector<int>a[MAXN];

inline int min(int rr,int tt)
{
	return rr<tt?rr:tt;
}


int main()
{
	int n,m,x,y;
	in>>n>>m;
	
	for(int i=1;i<=m;i++)
	{
		in>>x>>y>>cost[x][y];
		a[y].push_back(x);
	}
	
	for(int i=0; i < (1<<n) ;i++)
		for(int j=0;j<n; j++)
			if( i & (1<<j) ) // daca j e in configuratia lui i
				for(unsigned int k=0; k<a[j].size(); k++)//vecinii lui j
				{
					y=a[j][k];
					if( i & (1<<y) )
						c[i][j]= min ( c[i][j] , c[i ^ 	(1<<j) ][ y ] +cost[ y][ j] ) ;// minim intre configuratia curenta si configuratia cu j?
				}
				
	int sol=INF;
	for( int i=0;i< a[0].size();i++)
		sol=min(sol,c[1<<n -1][ a[0][i] ] +cost[ a[0][i] ][0] );// caut cel mai bun lant 
	if(sol==INF)
		out<<"Nu exista solutie" ;
	else
		out<<sol;
	return 0;
}