#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("hamilton.in");
ofstream fout("hamilton.out");

int main(){
	int n,m;
	fin >> n >> m;
	vector<vector<int>> v(n);
	vector<vector<int>> c(n, vector<int>(n, 1e9));
    
	for(int i = 0; i < m; i++){
		int x, y, cost;
		fin >> x >> y >> cost;
		v[y].push_back(x);
		c[x][y] = cost;
	}

	vector<vector<int>> dp((1 << n), vector<int>(n, 1e9));
    dp[1][0] = 0;
	for(int mask = 3; mask < (1 << n); mask += 2){
		for(int i = 0; i < n; i++){
			if(mask & (1 << i)){
				for(auto j : c[i]){
					if(mask & (1 << j))
					   dp[mask][i] = std::min(dp[mask][i], dp[mask ^ (1<<i)][j] + c[j][i]);

				}
			}
		}
	}
	int sol = 1e9;
	for(int i = 0; i < n; i++){
         sol = std::min(sol, dp[(1 << n)-1][i]+c[i][0]);
	}

	if(sol == 1e9){
		fout << "Nu exista solutie";
	}else{
		fout << sol;
	}

	return 0;
}