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

#define pb push_back
#define inf (1<<29)+100
#define NMax 18
#define LMax 1<<NMax

using namespace std;

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

int n,m;
int cost[NMax][NMax];
int C[LMax][NMax];
vector<int> V[NMax];

inline long long minim(long long a, long long b) {
	if (a < b)
		return a;
	return b;
}

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;
		V[b].pb(a);
		cost[a][b] = c;
	}
}

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 (int k=0;k<V[j].size();k++) {
					int intra = V[j][k];
					if (i & (1<<intra))
						C[i][j] = minim(C[i][j], C[i xor (1<<j)][intra] + cost[intra][j]);
				}
			}
	}

	long long answer = inf;
	lim--;
	for (int i=1;i<n;i++)
		answer = minim(answer, C[lim][i] + cost[i][0]);
	if (answer == inf) {g<<"Nu exista solutie\n"; return;}
	g<<answer<<'\n';
}

int main() {

	read();
	solve();

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