#include<fstream>
#include<vector>
using namespace std;
ifstream in("hamilton.in");
ofstream out("hamilton.out");

struct muchie{
	int nod, cost;
};

const int nmax = 18, inf = 1000000000;
vector <muchie> vecini[nmax];
int n, m, d[nmax][1<<nmax], rasp = inf;

int main(){
	int player_unu=0;

	in>>n>>m;
	for(int i = 1; i<=m; i++)
	{
		int x, y, c;
		muchie aux;

		in>>x>>y>>c;

		aux.nod = y;
		aux.cost = c;

		vecini[x].push_back(aux);
	}

	for(int i = 0; i<nmax; i++)
		for(int j = 0; j<(1<<nmax); j++)
			d[i][j] = inf;

	d[0][1] = 0;

	for(int mask = 1; mask<(1<<n) - 1; mask+=2)
	{
		for(int i = 0; (1<<i)<=mask; i++)
		{
			if(((1<<i) & mask)==(1<<i))
			{
				for(int j = 0; j<(int)vecini[i].size(); j++)
				{
					int aux = vecini[i][j].nod;
					if(((1<<aux) & mask)==0)
					{
						d[aux][mask | (1<<aux)] = min(d[aux][mask | (1<<aux)], d[i][mask] + vecini[i][j].cost);
					}
				}
			}
		}
	}

	int fmask = (1<<n) - 1;
	for(int i = 1; i<n; i++)
	{
		for(int j = 0; j<(int)vecini[i].size(); j++)
		{
			if(vecini[i][j].nod==0)
			{
				rasp = min(rasp, d[i][fmask] + vecini[i][j].cost);
			}
		}
	}

	if(rasp!=inf)
		out<<rasp<<'\n';
	else 
		out<<"Nu exista solutie\n";

	return player_unu;
}