#include <fstream>
#define LE 20
using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n,A[LE][LE],sum,st[LE],cost,rez,fr[LE],m,i,x,y;
void back(int k)
{
	if(k>n) {
		sum=0;
      for(int j=2;j<=n;++j) sum+=A[st[j-1]][st[j]];
	  if (A[st[n]][1]) {
		  sum+=A[st[n]][st[1]];
		  rez=min(rez,sum);
	  }
	}else 
	for(int i=1;i<=n;++i) if (fr[i]==0&&A[st[k-1]][i])
	{
		fr[i]=1;st[k]=i;
		back(k+1);fr[i]=0;
	}
}
int main()
{

	f>>n>>m;
	for(i=1;i<=m;++i)
	{
	  f>>x>>y>>cost;
	  A[x+1][y+1]=cost;
	}
	
	st[1]=1;fr[1]=1;
	rez=333333363;
	back(2);
	
	g<<rez<<'\n';
	f.close();g.close();
	return 0;
}