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

int v[20];
int a[18][18];
int cost[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];
		if(i==0)
			cost[j][(1<<i)|(1<<j)] = a[i][j];
	}

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

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

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

	return 0;
}