#include <iostream>
#include <fstream>
#include <vector>
using namespace std;


//ciclu hamilton de cost minim->infoarena

//1)backtracking - solutie O(n!)
//2)dp[mask][i] = drum de cost min care incepe in nodul 0 si se termina in nodul i si trece
//o sg data prin nodurile mask

//ex : fie n = 4 ; 0 1 2 3; noduri {1,2} <-> 0110

//dp[mask][i] =       min          c[j][i] + dp[mask- 2 ^i][j]       
//				i<= mask
//				(j,i) apartine E



const int NMAX = 20;
int c[NMAX][NMAX], dp[1 << NMAX][NMAX];
vector<int>in[NMAX];

int main() {

	int n, m;
	ifstream f("hamilton.in");
	f >> n >> m;

	for (int i = 0; i <= n; i++) {

		for (int j = 0; j <= n; j++) {

			c[i][j] = 1e9;
		}
	}

	while (m--) {

		int x, y, z;
		f >> x >> y >> z;

		in[y].push_back(x);
		c[x][y] = z;
	}
	f.close();

	for (int i = 1; i < (1<<NMAX); i++) {
	
		for (int j = 0; j < n; j++) {

			dp[i][j] = 1e9;
		}
	}

	dp[1][0] = 0;

	for (int mask = 1; mask < (1 << n); mask++) {

		for (int i = 1; i < n; i++) {

			if (mask& (1 << i)) {

				for (int k = 0; k < in[i].size(); k++) {

					int j = in[i][k];
					dp[mask][i] = min(dp[mask][i], dp[mask - (1 << i)][j] + c[j][i]);
				}

			}
		}
	}

	int res = 1e9;
	for (int i = 1; i < n; i++) {

		res = min(res, dp[(1 << n) - 1][i] + c[i][0]);
	}

	ofstream g("hamilton.out");
	if (res == 1e9)
		g << "Nu exista solutie";
	else
		g << res;
	g.close();
}