#include<fstream>
#include<vector>
#include<algorithm>
#define _NM 18
#define _MSK 1<<_NM
#define INF 1073741823
using namespace std;
typedef unsigned bitmsk;

vector<int> get_nodes(bitmsk x)
{
	vector<int> nds;
	for (int i=0;;i++)
	{
		if (x==0) break;
		if (x%2==1) nds.push_back(i);
		x >>= 1;
	}
	return nds;
}

int main()
{
	ifstream fin("hamilton.in");
	ofstream fout("hamilton.out");
	int nN,nM;
	fin>>nN>>nM;
	static int mCost[_NM][_NM];
	for (int i=1;i<=nM;i++)
	{
		int nod1,nod2,cost;
		fin>>nod1>>nod2>>cost;
		mCost[nod1][nod2]=cost;
	}
	static int lant[_MSK][_NM];
	bitmsk sol=(1<<nN)-1;
	
	for (bitmsk cur=1;cur<=sol;cur++)
	{
		vector<int> nds=get_nodes(cur);
		if (nds.size()>1) // else leave length cur 0
		for (vector<int>::iterator it_nowF=nds.begin();it_nowF!=nds.end();++it_nowF)
		{
			int dmin=INF;
			for (vector<int>::iterator it_oldF=nds.begin();it_oldF!=nds.end();++it_oldF)
			{
				if (it_oldF==it_nowF) continue;
				if (mCost[*it_oldF][*it_nowF])
					dmin=min(dmin, lant[cur ^ (1<<*it_nowF)][*it_oldF] + mCost[*it_oldF][*it_nowF]);
			}
			lant[cur][*it_nowF]=dmin;
		}
	}
	/////?????????????
	int dmin=INF;
	for (int vec=0;vec<nN;vec++)
	{
		if (mCost[vec][0]==0) continue;
		dmin=min(dmin, lant[sol][vec]+mCost[vec][0]);
	}
	fout<<dmin;
	/////////////
	return 0;
}