// hamilton
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

#define NMax 18
#define pb push_back
#define inf (1<<30)+100
#define LMAX 1<<18

using namespace std;

ifstream f("hamilton.in");
ofstream g("hamilton.out");

int n,m;
vector<int> V[NMax]; // V[a] = nodurile care intra cu muchie in a
int cost[NMax][NMax];
int C[LMAX][NMax];

void read() {
	f>>n>>m;
	for (int i=0;i<n;i++)
		for (int j=0;j<n;j++)
			cost[i][j] = inf;
	for (int i=1;i<=m;i++) {
		int a,b,c;
		f>>a>>b>>c;
		cost[a][b] = c;
		V[b].pb(a);
	}
}

void solve() {
	int lim = 1<<n;
	for (int i=0;i<lim;i++)
		for (int j=0;j<n;j++)
			C[i][j] = inf;

	// Ciclul ce contine doar nodul 0 (0b000001) si se termina in nodul 0 are costul 0
	C[1][0] = 0;

	// PD
	for (int i=0;i<lim;i++)
		for (int j=0;j<n;j++)
			if (i & (1<<j))
				for (int k=0;k<V[j].size();k++) {
					if (i & (1<<V[j][k])) {
						C[i][j] = min(C[i][j], C[i xor (1<<j)][V[j][k]] + cost[V[j][k]][j]);
					}
				}

	int sol = inf;
	lim--;
	for (int i=0;i<V[0].size();i++)
		sol = min(sol, C[lim][V[0][i]] + cost[V[0][i]][0]);

	if (sol == inf)
		g<<"Nu exista solutie\n";
	else
		g<<sol<<'\n';
}

int main() {

	read();
	solve();

	f.close(); g.close();
	return 0;
}