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

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