#include <fstream>
#include <vector>
#define MAXN 20
#define MAXX (1<<18)
#define INF 0xfffffff
using namespace std;
ifstream f("hamilton.in");  ofstream g("hamilton.out");
vector<int> G[MAXN];
int M , N , C[MAXX][MAXN] , Cost[MAXN][MAXN];
int main()
{	f>>N>>M;
	for(int i=0; i<N; ++i) for(int j=0; j<N; ++j) Cost[i][j] = INF;
	for(;M;M--) {int x , y; f>>x>>y; G[y].push_back(x); f>>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(int k=0; k<G[j].size(); ++k)
					if(i & (1<<G[j][k]))
						C[i][j] = min(C[i][j],C[i ^ (1<<j)][G[j][k]] + Cost[G[j][k]][j]);

	int sol = INF;
	for(int i=0; i<G[0].size(); ++i)
		sol = min(sol,C[(1<<N) - 1][G[0][i]] + Cost[G[0][i]][0]);
	if(sol==INF) g<<"Nu exista solutie\n"; else g<<sol<<'\n';
	return 0;
}
/*
#include <fstream>
#include <vector>

using namespace std;

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

const int MAXN = 20, MAXX = 1<<18 , INF = int(2e9);

vector<int> G[MAXN];
int M , N , C[MAXX][MAXN] , Cost[MAXN][MAXN];

int main()
{
	fin>>N>>M;
	for(int i=0;i<N;++i)
		for(int j=0;j<N;++j)
			Cost[i][j] = INF;

	for(;M;M--)
	{
		int x , y;
		fin>>x>>y;
		G[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<G[j].size();++k)
					if(i & (1<<G[j][k]))
						C[i][j] = min(C[i][j],C[i ^ (1<<j)][G[j][k]] + Cost[G[j][k]][j]);

	int sol = INF;
	for(size_t i=0;i<G[0].size();++i)
		sol = min(sol,C[(1<<N) - 1][G[0][i]] + Cost[G[0][i]][0]);
	if(sol==INF)
		fout<<"Nu exista solutie\n";
	else fout<<sol<<'\n';
	return 0;
}
*/