#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*/);
	
	
	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;
}