#include<fstream>
using namespace std;
int h[300000][18],ii[18][18],n,m,i,j,k,x,p;
void oper()
{for(i=0;i<p;++i)
  for(j=0;j<n;++j)
    if((i&(1<<j)))
      for(k=0;k<n;++k)
        if(k!=j && (i&(1<<k)))
          if(h[i][j]>h[i^(1<<j)][k]+ii[k][j])
            h[i][j]=h[i^(1<<j)][k]+ii[k][j];
x=h[p-1][0];
for(i=1;i<n;++i)
  if(h[p-1][i]+ii[i][0]<x)
   x=h[p-1][i]+ii[i][0];}
int main()
{ifstream q("hamilton.in");
ofstream w("hamilton.out");
q>>n>>m;
for(i=0;i<n;++i)
 for(j=0;j<n;++j)
   ii[i][j]=5400000;
for(i=1;i<=m;++i)
  {q>>x>>j>>p;
  ii[x][j]=p;}
p=1<<n;
for(i=0;i<p;++i)
  for(j=0;j<n;++j)
    h[i][j]=5400000;
h[1][0]=0;
oper();
if(x==5400000)
 w<<"Nu exista solutie\n";
else
 w<<x<<"\n";
return 0;}