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

int n ,m ,matrice[20][20] ,D[20][300000];

void Citire()
	{  
	    ifstream f("hamilton.in");
		int x,y,z;
		f >> n >> m;;
		for(int i = 1; i <= m ; i++)
		{
			f >> x >> y >> z;
			matrice[x][y] = z;
		}
		
		for(int i = 0; i < n; i++)
			for(int j = 0; j < (1<<n); j++)
				D[i][j] = 10000000009;
		D[0][1] = 0;
	}
	
	void Rezolva(int &max)
	{
		for(int i = 1; i < (1<<n); i++)
			for(int nod = 0; nod < n; nod++)
				if(((i & (1 << nod)) != 0))
					for(int j = 0; j < n; j++)
						if(matrice[nod][j] && ((i & (1 << j)) == 0))
							if(D[j][i + (1 << j)] > D[nod][i] + matrice[nod][j])
								D[j][i+(1<<j)] = D[nod][i] + matrice[nod][j];
					
		for(int i = 0; i < n; i++)
			if(D[i][((1<<n) - 1)] + matrice[i][0] < max && matrice[i][0])
				max = D[i][(1<<n) - 1] + matrice[i][0];
	}
	
	void Verifica(int &max)
	{		
	    ofstream g("hamilton.out");
		if(max==1000000009)
			g << "Nu exista solutie!";
		else
			g << max << endl;
	} 

int main()
{
  
	int max = 1000000009;
	Citire();
	Rezolva(max);
	Verifica(max);

	return 0;
}