#include<stdio.h>
#include<vector>
#define NMAX 20
#define XMAX 262150 //aprox 1<<18 , limita maxima a lui n
#define INF 1<<30
using namespace std;

FILE *in,*out;
int cost[NMAX][NMAX],x,y;
vector<int> A[NMAX];
int C[XMAX][NMAX];
int main()
{
	in=fopen("hamilton.in","rt");
	out=fopen("hamilton.out","wt");
	fscanf(in,"%d %d",&n,&m);
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			cost[i][j]=INF;
	for(i=1;i<=m;i++)
	{
		fscanf(in,"%d %d",&x,&y);
		A[y].push_back(x);
		fscanf(in,"%d",&cost[x][y]);
	}
	
	for(i=0; i<1<<n ;i++)
		for(j=0;j<n;j++)
			C[i][j]=INF;
	C[1][0]=0;
	
	for(i=0; i<1<<n ;i++)
		for(j=0;j<n;j++)
			if(i & (1<<j) )
			{
				for(int k=0;k<A[j].size();k++)
					if(i &