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


//#define __DEBUG__

using namespace std;

typedef unsigned int DWORD;
typedef unsigned char BYTE;

#define MAXN 18
const DWORD INFINITE = 1 << 30;


const char infile[] = "hamilton.in";
const char outfile[] = "hamilton.out";

typedef unsigned int DWORD;
typedef unsigned char BYTE;

DWORD numarNoduri;
DWORD numarMuchii;

vector< pair < DWORD, DWORD> > Graph[MAXN];

DWORD vectorSolutie[MAXN];
bool isVisited[MAXN];

DWORD minTotal = INFINITE;
DWORD cstSoFar = 0;

void CitesteInput()
{
	fstream fin(infile, ios::in);

	fin >> numarNoduri
		>> numarMuchii ;

	DWORD src;
	DWORD dst;
	DWORD cst;

	for ( DWORD i = 0; i < numarMuchii; i++ )
	{
		fin >> src
			>> dst
			>> cst;

		Graph[src].push_back(make_pair(dst, cst) );
	}

	fin.close();
}


void BKT(DWORD k)
{
	if(k == numarNoduri)
	{

		bool existaCiclu = false;
		DWORD costUltimaMuchie;

		for ( vector< pair < DWORD, DWORD> >::iterator itr = Graph[ vectorSolutie[ k - 1 ] ].begin();
			itr != Graph[ vectorSolutie [ k -1 ] ].end();
			itr++ )
		{
			if( itr->first == 0)
			{
				existaCiclu = true;
				costUltimaMuchie = itr->second;
				break;
			}
		}

		if(existaCiclu == false)
			return;
		
		minTotal = ( cstSoFar + costUltimaMuchie ) < minTotal ? ( cstSoFar + costUltimaMuchie ) : minTotal;
		

#ifdef __DEBUG__

		for( DWORD i = 0 ; i < numarNoduri; i++)
		{
			cout << vectorSolutie[i] << " " ;

		}
		cout << "\n";

#endif

	}
	else
	{
		if( k == 0)
		{
			vectorSolutie[k] = 0;
			cstSoFar = 0;
			isVisited[0] = true;

			BKT(k+1);
		}
		else
		{
			for ( vector< pair < DWORD, DWORD> >::iterator itr = Graph[ vectorSolutie[ k - 1 ] ].begin();
				itr != Graph[ vectorSolutie [ k -1 ] ].end();
				itr++ )
			{
				if ( isVisited[itr->first] == false)
				{
					vectorSolutie[k] = itr->first;

					isVisited[itr->first] = true;
					cstSoFar += itr->second;

					BKT( k + 1);

					isVisited[itr->first] = false;
					cstSoFar -= itr->second;
				}
			}
		}
		
	}
}


void ScrieOutput()
{
	fstream fout(outfile, ios::out);

	if( minTotal == INFINITE)
	{
		fout << "Nu exista solutie\n";
	}
	else
	{
		fout << minTotal << "\n";
	}
	fout.close();

}


int main(int argc, char*argv[])
{
	CitesteInput();
	BKT(0);
	ScrieOutput();
}