using namespace std;

#include <fstream>
#include <vector>
#include <climits>

#define mp make_pair
#define pb push_back

vector<int> G[20];

int n, uz[20], x[20], smin = INT_MAX,a[20][20];

void read(){
	ifstream fin("hamilton.in");
	fin>>n;
	int m;
	fin>>m;
	for( ; m ; --m){
		int i,j,c;
		fin>>i>>j>>c;
		G[i].pb(j);
		a[i][j]=c;
	}
	
}
void back(int k, int S){
	if(k==n){
		if( a[x[n-1]][0] && S+a[x[n-1]][0]<smin)
			smin = S+a[x[n-1]][0];
	}
	else
	  for(vector<int>::iterator I=G[x[k-1]].begin(); I < G[x[k-1]].end() ; ++I)
		if(uz[*I]==0)
		{
			uz[*I]=1;
			x[k]=*I;
			if(S+a[x[k-1]][*I]<smin)
				back(k+1,S+a[x[k-1]][*I]);
			uz[*I]=0;
		}
}
void write(){
	ofstream fout("hamilton.out");
	if(smin==INT_MAX)
		fout << "Nu exista solutie";
	else
		fout << smin << endl;
}

int main(){
	read();
	x[0]=0;
	uz[0]=1;
	back(1,0);
	write();
	return 0;
}