# include <iostream>
# include <fstream>
# include <algorithm>
# include <vector>

using namespace std;

const int inf = 0x3f3f3f3f, MAXN = 18;

struct neighbour{
	int id, cost;
};

bool G [ MAXN ] [ MAXN ];
int C [ MAXN ] [ MAXN ];
int n, m;
int p [ MAXN + 1 ];
int cst = inf;
bool viz [ MAXN ];

void dfs ( int nd, int kst, int cnt ){
	viz [ nd ] = true;
	int i;
	if ( cnt < n ){
		for ( i = 0; i < n; ++ i )
			if ( ! viz [ i ] && G [ nd ] [ i ] )
				dfs ( i, kst + C [ nd ] [ i ], cnt + 1 );
	}
	else{
		if ( G [ nd ] [ 1 ] )
			if ( kst + C [ nd ] [ 1 ] < cst )
				cst = kst + C [ nd ] [ 1 ];
	}
	viz [ nd ] = false;
}

int main(){
	
	int i, node1, node2, kst;
	
	ifstream f ( "hamilton.in" );
	
	f >> n >> m;
	
	for ( i = 0; i < m; ++ i ){
	
		f >> node1 >> node2 >> kst;
		G [ node1 ] [ node2 ] = true;
		C [ node1 ] [ node2 ] = kst;
		
	}
	
	for ( i = 0; i < n; ++ i )
		p [ i ] = i;
	
	f . close();
	
	dfs ( 1, 0, 1 );
	
	ofstream g ( "hamilton.out" );
	
	if ( cst == inf )
		g << "Nu exista solutie\n";
	else
		g << cst << '\n';
	
	g . close ();
	
	return 0;
}