#include<iostream>
#include<fstream>
#include<vector>
#include<math.h>
#include<string.h>

using namespace std;

const int MAX_N=20, MAX_CONF=pow(2,18)+1, INF=1000000*18*(18-1)+1;

int n,m, cost[MAX_N][MAX_N];
int c[MAX_CONF][MAX_N];
vector<int> graf[MAX_N];


int calc(int conf, int last){
	if(c[conf][last]==-1){
		c[conf][last]=INF;
		for(size_t i=0;i<graf[last].size();i++) //parcurg nodurile care arata spre ultimul nod din lant
		  if(conf & (1<<graf[last][i]) ){ //aleg doar nodurile din lant
			if( 0==graf[last][i] && conf != (1<<last) + 1 ) continue;  //pe 0 il scot ultimul
		    c[conf][last]=min( c[conf][last], calc( conf ^ (1<<last), graf[last][i] ) + cost[ graf[last][i] ][last] );
		 }
	}
	return c[conf][last];
}


int main(){
 ifstream in("hamilton.in"); ofstream out("hamilton.out");
 int i,j, x, y, z;
 int sol=INF;
 in>>n>>m; 
 
 for(i=0;i<n;i++) 
    for(j=0;j<n;j++) 
	    cost[i][j]=INF;   

 for(i=0;i<m;i++){
 	in>>x>>y>>z;
 	cost[x][y]=z;
 	graf[y].push_back(x);  //muchia inversa
 }		 
 
 memset(c,-1,sizeof(c));
 c[1][0]=0;
 
 for(size_t i=0;i<graf[0].size();i++)
     sol=min(sol, calc( pow(2,n)-1 , graf[0][i] ) + cost[ graf[0][i] ][0] );
  
 if(sol==INF) out<<"Nu exista solutie";
 else out<<sol; 
 
 in.close(); out.close();	
 return 0;	
}