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

	minimum = INF;
	for (int j = 0; j < adj[0].size(); ++j)
		minimum = min(minimum, drumposib[Nmax - 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;
}