#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <algorithm>

int main ()
{
	std::ifstream in("hamilton.in");
	
	int N, M;
	in >> N >> M;
	
	std::vector<std::vector<int> > adj(N);
	std::vector<std::vector<int> > cost(N, std::vector<int>(N, -1));
	std::vector<std::vector<int> > din(1<<N, std::vector<int>(N, INT_MAX/2));
	
	for (int i = 0; i < M; ++ i) {
		int x, y, c;
		in >> x >> y >> c;
		adj[y].push_back(x);
		
		cost[x][y] = c;
	}
	
	in.close();
	
	din[1][0] = 0;
	for (int i = 2; i < (1<<N); ++ i) {
		for (int j = 1; j < N; ++ j) {
			if (i & (1 << j)) {
				for (auto k : adj[j]) {
					if (i && (1 << k)) {
						din[i][j] = std::min(din[i][j], din[i^(1<<j)][k] + cost[k][j]);
					}
				}
			}
		}
	}
	
	std::ofstream out("hamilton.out");
	
	int minValue = INT_MAX/2;
	for (int i = 1; i < N; ++ i) {
		if (cost[i][0] >= 0) {
			minValue = std::min(minValue, din[(1<<N)-1][i] + cost[i][0]);
		}
	}
	
	if (minValue >= INT_MAX/2) {
		out << "Nu exista solutie\n";
	} else {
		out << minValue << "\n";
	}
	
	out.close();
	
	return 0;
}