#include<fstream>
#include<vector>
using namespace std;

const int MAXN = 21;
const int MAXX = 1<<19;
const int INF = 100000000;


int cost[MAXN][MAXN];
int c[MAXX][MAXN];

vector <int> a[MAXN];

int n,m;

inline int min(int x,int y)
{
	return x<y ? x : y;
}

int main()
{
	ifstream in("hamilton.in");
	
	ofstream out("hamilton.out");
	in>>n>>m;
	
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cost[i][j]=INF;
	
	for(int i=1;i<=m;i++)
	{
		int x,y;
		in>>x>>y;
		in>>cost[x][y];
		a[y].push_back(x);
	}
	
	for(int i=0;i< (1<<n); i++)
		for( int j=0;j<n;j++)
			c[i][j]=INF;
	c[1][0]=0;
	
	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(size_t k=0; k< a[j].size(); k++)//vecinii lui j
				{
					int y;	
					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( size_t 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\n" ;
	else
		out<<sol<<"\n";
	return 0;
}