using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<cstring>
#define oo 0x3f3f3f3f
#define pb push_back
vector<int> G[18];
int c[18][18];
int dp[(1<<18)][18],N,M;
ofstream fout("hamilton.out");
void cit()
{int x,y,co,i;
    ifstream fin("hamilton.in");
    fin>>N>>M;

    memset(c,oo,sizeof(c));
    for(i=1;i<=M;i++)
    {
        fin>>x>>y>>co;
        G[y].pb(x);   // le pun invers ca eu merg de la config completa la config goala
        c[x][y]=co;
    }


}

int memo(int start,int conf,int end )
{int i;
 //cout<<end<<" ";
    if(dp[conf][end]==-1)
    {   dp[conf][end]=oo;
        for(i=0;i<G[end].size();i++)
         if(conf & (1<<G[end][i]))
          if(!(G[end][i]==start && ((conf^(1<<end))!=(1<<start))))

           dp[conf][end]=min(dp[conf][end], memo(start,conf^(1<<end),G[end][i]) +c[G[end][i]][end]);


    }

    return dp[conf][end];
}

void solve()
{int i,j,sol=oo;
  for(i=0;i<N;i++)
  {

      memset(dp,-1,sizeof(dp));

      dp[1<<i][i]=0;
      for(j=0;j<G[i].size();j++)
      {
         sol=min(sol,memo(i,(1<<N)-1,G[i][j])+c[G[i][j]][i]);
         //cout<<"\n";
      }
      //cout<<"\n";

  }
  if(sol!=oo)
  fout<<sol<<"\n";
  else fout<<"Nu exista solutie \n";

}

int main()
{
    cit();
    memset(dp,-1,sizeof(dp));
    solve();

    return 0;
}