#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>
using namespace std;

int v[20];
int a[18][18];
int cost[18][18][1<<18];
int i, j, k, l, n, m;

void init()
{
	for(int i=0;i<20;++i)
		v[i] = 1 << i;
	memset(cost, 0x7f, sizeof(cost));
}

int main()
{
	init();
	ifstream cin("hamilton.in");
	ofstream cout("hamilton.out");

	cin >> n >> m;
	while(m--)
	{
		cin >> i >> j;
		cin >> a[i][j];
		cost[i][j][(1<<i)|(1<<j)] = a[i][j];
	}

	int N = 1<<n;
	for(k=0;k<N;++k)
		for(i=0;i<n;++i)
		if(k & v[i])
			for(j=0;j<n;++j)
			if(k & v[j] && i != j)
				for(l=0;l<n;++l)
					if(!(k & v[l]) && a[j][l])	
						cost[i][l][k | v[l]] = cost[i][j][k] + a[j][l];

	int aux = 20000000;
	bool found = false;	
	int min = 0x7fffffff;
	-- N;
	for(i=0;i<n;++i)
		for(j=0;j<n;++j)
			if(cost[i][j][N] < aux && a[j][i])
				found = true, min = std::min(min, cost[i][j][N] + a[j][i]);

	if (!found)
	    cout << "Nu exista solutie" << endl;
	else
	    cout << min << endl;

	return 0;
}