#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 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)) {
				int cost = dp[msk][j], nnode, ncost;

				for(auto [nnode, ncost] : muci[j]) {
					if(!((1 << nnode) & msk))
						dp[(msk | (1 << nnode))][nnode] = min(dp[(msk | (1 << nnode))][nnode], cost + ncost);
				}
			}
		}
	}
}

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

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

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

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