#include <fstream>
#include <vector>
using namespace std;

ofstream fout("hamilton.out");

const int MaxN = 18, 
		  MaxB = 1 << 18, 
		  Inf = 0x3f3f3f3f;


vector<int> G[MaxN];
int C[MaxB][MaxN];
int w[MaxN][MaxN];
int n, m;

void Read();
void Hamilton();


int main()
{
	Read();
	Hamilton();
	
	fout.close();
}


void Hamilton()
{
	for (int i = 0; i < 1 << n; ++i)
		for (int j = 0; j < n; ++j)
			C[i][j] = Inf;
	
	
	for (int i = 0; i < n; ++i )
		C[1 << i][i] = 0;
	
	for (int i = 1; i < 1 << n; ++i) // pt fiecare submultime i
		for (int j = 0; j < n; ++j )
			if ( i & (1 << j) )     // daca j este in masca i 
					for ( const int& k : G[j] )
						if ( (i & (1 << k)) == 0 ) // k nu apartine sumbmultimii i
							C[i | (1 << k)][k] = min(C[i | (1 << k)][k], C[i][j] + w[j][k]);
	
	
	int cmin = Inf;   // presup 0 e inceputul lantului care contine toate nodurile
	for (int i = 1; i < n; ++i)
		cmin = min(cmin, C[(1 << n) - 1][i] + w[i][0]); 
	
	fout << cmin << '\n';
}

void Read()
{
	ifstream fin("hamilton.in");

	int x, y, c;
	fin >> n >> m;
	
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			w[i][j] = Inf;
	
	for (int i = 0; i < m; ++i)
	{
		fin >> x >> y >> c;
		G[x].push_back(y);
		w[x][y] = c;
	}
	fin.close();
	
}