//https://infoarena.ro/problema/hamilton
//comentarii ce au ajutat la intelegerea rezolvarii aici https://infoarena.ro/job_detail/2787479?action=view-source
//plus rezolvarea autorului (fara comentarii) https://infoarena.ro/job_detail/381350?action=view-source
#include <fstream>
#include <vector>

using namespace std;

const int MAXN = 18;
const int MAXX = 307;
const int INF = 1000000;

int N, M, minimum;
int cost[MAXN][MAXN];
int drumposib[MAXX][MAXN];
vector <int> adj[MAXN];

int main()
{
	ifstream f("hamilton.in");
	ofstream g("hamilton.out");

	f >> N >> M;
	//initial, costurile muchiilor intre care nu exista drum sunt INF
	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;

		f >> x >> y;
		adj[y].push_back(x);//ne intereseaza ce noduri ajung in nodul x
		f >> cost[x][y];
	}

	//initial, toate drumurile posibile sunt INF
	for (int i = 0; i < (1 << N); ++i)
		for (int j = 0; j < N; ++j) 
			drumposib[i][j] = INF;

	drumposib[1][0] = 0;//la calculul drumului de cost minim, 
	//consideram ca la parcurgerea incepand cu bitul 0, e setat 1, dar ajungem in 0 si trebuie sa fie 0 

	for (int mask = 0; mask < (1 << N); ++mask) //toate submultimile posibile mask 2^N, deci fiecare combinatie de n noduri
		for (int i = 0; i < N; ++i) //toate nodurile posibile i de adaugat in drumposibil, nodul curent de pus
			if (mask & (1 << i)) //daca i apartine multimii determinate de mask <=> al i-lea bit al lui mask este 1; nodul i in combinatia de noduri pe care o verificam 
			  //for (int k = 0; k < adj[i].size(); ++k) //iau nodurile k pentru care exista arcul (k,i) 
				for (auto k: adj[i]) //iau nodurile k pentru care exista arcul (k,i) 	
				 if (mask & (1 << adj[i][k])) //si verific daca acestea apartin lui mask, daca da
						drumposib[mask][i] = min(drumposib[mask][i], drumposib[mask ^ (1 << i)][adj[i][k]] + cost[adj[i][k]][i]);
						//drumposib[mask][i] =  min(drumposib[mask][i],drumposib[mask - {i}][vecin] + cost[vecin][i])

	minimum = INF;
	//for (int j = 0; j < adj[0].size(); ++j)
	 for (auto j: adj[0])
		minimum = min(minimum, drumposib[(1 << N) - 1][adj[0][j]] + cost[adj[0][j]][0]);

	if (minimum == INF) 
		g << "Nu exista solutie" << endl;
	else 
		g << minimum << endl;

	f.close();
	g.close();
	
	return 0;
}