#define MAX_N 18
#define INF (1 << 30)
 
#include <fstream>
#include <bitset>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;
 
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");
 
int n, m, cnt, rasp = INF, sumAux/*, Aux[MAX_N + 1], R[MAX_N + 1]*/;
vector<tuple<int, int>> G[MAX_N + 1];
bitset<MAX_N + 1> F;
 
void Df(int nod/*, int k*/);
 
int main()
{
	fin >> n >> m;
	for (int i = 0, x, y, c; i < m; ++i)
	{
		fin >> x >> y >> c;
		++x;
		++y;
		G[x].emplace_back(y, c);
	}
	
	Df(1/*, 1*/);
	
	if (rasp == INF)
	{
		fout << "Nu exista solutie";
	}
	else
	{
		fout << rasp;
	}
	/*
	fout << '\n';
	for (int i = 1; i <= n; ++i)
	{
		fout << R[i] << ' ';
	}
	fout << R[1];
	*/
	
	fin.close();
	fout.close();
	return 0;
}
 
/*
void Salveaza()
{
	for (int i = 1; i <= n; ++i)
	{
		R[i] = Aux[i];
	}
}
*/
 
void Df(int nod/*, int k*/)
{
	F[nod] = true;
	//Aux[k] = nod;
	++cnt;
	
	if (cnt == n)
	{
		for (const auto& vecin : G[nod])
		{
			if (get<0>(vecin) == 1)
			{
				sumAux += get<1>(vecin);
				/*
				if (sumAux < rasp)
				{
					Salveaza();
				}
				*/
				rasp = min(rasp, sumAux);
				sumAux -= get<1>(vecin);
				break;
			}
		}
	}
	else
	{
		for (const auto& vecin : G[nod])
		{
			if (!F[get<0>(vecin)])
			{
				sumAux += get<1>(vecin);
				Df(get<0>(vecin)/*, k + 1*/);
				sumAux -= get<1>(vecin);
			}
		}
	}
	
	F[nod] = false;
	--cnt;
}