#include <fstream>
#include <vector>

#define NMAX 18
#define MMAX 306
#define INF 100000000

using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int n, m;


vector<int> arc[NMAX+5];
int cost[NMAX+5][NMAX+5];
int c[(1<<NMAX)+5][NMAX];


int main()
{
	fin>>n>>m;
	
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			cost[i][j]=INF;	

	for(int i=0; i<m; i++)
	{
		int x, y;
		fin>>x>>y;
		arc[y].push_back(x);
		fin>>cost[x][y];
	}
	
	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))
				for(size_t k=0; k<arc[j].size(); k++)
					if(i&(1<<arc[j][k]))
						c[i][j]=min(c[i][j], c[i^(1<<j)][ arc[j][k] ]+cost[ arc[j][k] ][j]);
				
	}	
	
	int sol=INF;
	for(size_t i=0; i<arc[0].size(); i++)
		sol=min(sol, c[(1<<n)-1][arc[0][i]]+cost[arc[0][i]][0]);

	if(sol==INF)
		fout<<"Nu exista solutie"<<endl;
	else
		fout<<sol<<endl;
	return 0;
}