#include <vector>
#include <fstream>
#include <cstdlib>
#define N_MAX 20
#define oo 1<<29
#define pr pair< int, int>

using namespace std;
bool was[N_MAX];
bool isF0[N_MAX];
int costF0[N_MAX];
int N, cost=0, costMin=oo;
vector< int > c;
vector< pr > G[N_MAX];
inline void DFS( int x, int countN )
{
	if( countN == N && isF0[x] )
	{

		if( costMin > cost+costF0[x] )
			costMin=cost+costF0[x];
		return;
	}
	vector<pr>::const_iterator it, iend;
	for( it=G[x].begin(), iend=G[x].end(); it < iend; ++it )
		if( false == was[it->first] )
		{
			was[it->first]=true;
			cost+=it->second;
			c.push_back( it->first );
			DFS( it->first, countN+1 );
			c.pop_back();
			cost-=it->second;
			was[it->first]=false;
		}
}
int main( void )
{
	int M, x, y, cc;
	ifstream in( "hamilton.in" );
	for( in>>N>>M; M; --M )
	{
		in>>x>>y>>cc;
		G[x].push_back( pr( y, cc ) );
		if( y == 0 )
			isF0[x]=true, costF0[x]=cc;
	}
	was[0]=true;
	c.push_back(0);
	DFS( 0, 1 );
	ofstream out( "hamilton.out" );
	out<<costMin<<'\n';
	return EXIT_SUCCESS;
}