#include <bits/stdc++.h>

using namespace std;

ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

const int nmax = 19, inf = 79797979, mskmax = (1 << 18);
vector<pair<int, int>> muci[nmax];
int dp[mskmax][nmax], c[nmax];
int n, m, x, y, g;
bool debug = 0;

void rid() {
	fin >> n >> m;

	for(int i = 0; i < n; i++)
		c[i] = inf;

	for(int i = 1; i <= m; i++) {
		fin >> x >> y >> g;
		muci[x].push_back({y, g});

		if(y == 0)
			c[x] = g;
	}
}

void update_(int mask, int node) {
	int nmask, cost = dp[mask][node];
	if(dp[mask][node] == inf)
		return;

	for(pair<int, int> muc : muci[node]) {
		int nnode = muc.first, ncost = muc.second;

		if(!((1 << nnode) & mask)) {
			nmask = (mask | (1 << nnode));
			dp[nmask][nnode] = min(dp[nmask][nnode], cost + ncost);
		}
	}
}

void meic_depe() {
	for(int i = 0; i <= n; i++)
		for(int j = 0; j < (1 << (n)); j++)
			dp[j][i] = inf;
	dp[1][0] = 0;

	for(int msk = 1; msk < (1 << (n)); msk++) {
		for(int j = 0; j <= n; j++) {
			if(((1 << j) & msk))
				update_(msk, j);
		}
	}
}

int get_sol() {
	int all = (1 << (n)) - 1, rez = inf;

	for(int i = 0; i < n; i++)
		rez = min(rez, dp[all][i] + c[i]);

	return rez;
}

void print() {
	int rez = get_sol();

	if(rez == inf)
		fout << "Nu exista solutie\n";
	else
		fout << rez;
}

int main() {
	rid();
	meic_depe();
	print();
	return 0;
}