//https://www.infoarena.ro/problema/hamilton
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("fast-math")
//#pragma GCC optimize ("unroll-loops")
//#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <vector>
//#include <cstring>
//#include <cmath>
//#include <bitset>
//#include <queue>
//#include <stack>
//#include <utility>
//#include <algorithm>
//#include <string>
//#include <map>
//#include <unordered_map>
//#include <set>
//#include <unordered_set>
//#include <cstdint>
//#include <climits>
//#include <iomanip>
//#include <cstdio>
//#include <tuple>
using namespace std;

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

const int INF = 0x3f3f3f3f;
const int NRMAX = 18;

vector <vector <pair <int, int>>> gr;
int d[1 << NRMAX][NRMAX], rez = INF;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n, m, i, x, y, c;

	fin >> n >> m;
	gr.resize(n);

	for (i = 1; i <= m; ++i)
	{
		fin >> x >> y >> c;
		gr[y].emplace_back(x, c);
	}

	memset(d, INF, sizeof d);

	d[1][0] = 0;
	for (int masca = 3; masca < (1 << n); ++masca)
	{
		for (i = 0; i < n; ++i)
		{
			if (masca & (1 << i))
			{
				int j = masca ^ (1 << i);

				for (const auto& it : gr[i])
				{
					if (j & (1 << it.first))
						d[masca][i] = min(d[masca][i], d[j][it.first] + it.second);
				}
			}
		}
	}

	for (const auto& it : gr[0])
	{
		int j = (1 << n) - 1;
		rez = min(rez, d[j][it.first] + it.second);
	}

	if (rez == INF)
		fout << "Nu exista solutie";
	else
		fout << rez;

	return 0;
}