#include<fstream.h>
#define INF 1000000000
long a[19][19]={{0}},lg[19]={0},lgmin=INF,d;
int n,v[19]={0},m,j,k;

long ham(int k,int j)
{int i;
if(k-1==n&&a[j][1]&&lg[n]+a[j][1]<lgmin)
       return lg[n]+a[j][1];
for(i=2;i<=n;i++)
if(!v[i]&&a[j][i]&&(lg[k]=lg[k-1]+a[j][i])<lgmin)
       {v[i]=1;
       lgmin=ham(k+1,i);
       v[i]=0;}
return lgmin;}
               
int main()
{ifstream f("hamilton.in");
ofstream h("hamilton.out");
f>>n>>m;
while(m--)
       {f>>j>>k>>d;
       a[j+1][k+1]=d;}
if((lgmin=ham(2,1))==INF)
       h<<"Nu exista solutie";
else
       h<<lgmin;
f.close();
h.close();
return 0;}