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

#define pb push_back
#define inf (1<<29)+100
#define NMax 18
#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 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;
	C[1][0] = 0;

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

	int sol = inf;
	lim--;
	for (int i=0;i<n;i++) {
		sol = min(sol, C[lim][i] + cost[i][0]);
	}

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

int main() {

	read();
	solve();

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