#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;
}