// Un ciclu hamiltonian este definit ca un circuit pronind de la nodul 
// de inceput si parcurgand toate nodurile. Putem defini un ciclu hamiltonian 
// de cost minim. Pentru a il determina vom folosi o dinamica O( M*2^N )
// in care D[i][j] = costul minim al unui ciclu care incepe din nodul
// de start si ajunge in nodul i , folosind nodurile din reprezentarea binara
// a numarului j. 
// Pentru a rezolva problema mai eficient ( din punctul de vedere al memoriei )
// putem constru cu Roy-Floyd un vector de transcriere a starilor , eliminand
// starile inutile. Acest procedeu , anume eliminarea starilor inutile , se 
// numeste memoizare.

#include <fstream>
#include <vector>

using namespace std;

const int Maxn = 20;
const int Maxv = 262150; // > 1<<18
const int oo = 1<<30;

int N, M, Sol;
int Cost[Maxn][Maxn];
int C[Maxv][Maxn];
vector <int> Leg[Maxn];

int main()
{
	ifstream F("hamilton.in");
	ofstream G("hamilton.out");

	F >> N >> M;

	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j) Cost[i][j] = oo;

	for (int i = 1; i <= M; ++i)
	{
		int x, y;

		F >> x >> y;
		Leg[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] = oo;

	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 < Leg[j].size(); ++k)
					if (i & (1<<Leg[j][k]))
						C[i][j] = min(C[i][j], C[i ^ (1<<j)][ Leg[j][k] ] + Cost[ Leg[j][k] ][j]);

	Sol = oo;
	for (size_t i = 0; i < Leg[0].size(); ++i)
		Sol = min(Sol, C[(1<<N) - 1][ Leg[0][i] ] + Cost[ Leg[0][i] ][0]);

	if (Sol == oo) 
		G << "Nu exista solutie" << endl;
	else 
		G << Sol << endl;
}