#include <fstream>
#define inf 1000000000
using namespace std;
ifstream fin ("hamilton.in");
ofstream fout ("hamilton.out");
int n, m;
int a[50][50];
int t[50];
int tmin[50];
int lgt, lgmin=inf;
int uz[50];
void gen (int k);
int main()
{int i, j, r, x;
 t[1]=1; uz[1]=1;
 fin>>n>>m;
 for (r=1; r<=m; r++)
	 {fin>>i>>j>>x;
	  a[i+1][j+1]=x;
	 }
gen (2);
if (lgmin==inf)
	fout<<"Nu exista solutie";
else
fout<<lgmin;
/*for (r=1; r<=n; r++)
      cout<<tmin [r-1]<<' ';
}*/
    return 0;

}
void gen (int k)
{int s;
 if (lgt>lgmin)
	 return;
 if (k==n+1)
 {
	if (a[t[n]][1]!=0 && lgt+a[t[n]][1] < lgmin)
	 {for (s=1; s<=n; s++)
		    tmin[s]=t[s];
	  lgmin=lgt+a[t[n]][1];;
	 }
 }
 else
 {

  for (s=1; s<=n; s++)
		 {if (uz[s]==0 && a[t[k-1]][s]!=0 )
			{t[k]=s;
			  uz[s]=1;
			 lgt=lgt+a[t[k-1]][t[k]];
			 gen (k+1);
			 lgt=lgt-a[t[k-1]][t[k]];
			 uz[s]=0;
			}
		 }
 }
}