#include <fstream>
#include <vector>

#define pb push_back

const int MAXN = 18;
const int MAXMASK = 1<<18;
const int INF = (1<<29)-1;

using namespace std;

ifstream cin( "hamilton.in" );
ofstream cout( "hamilton.out" );

int n, m;

vector<int> g[MAXN+1];

int weight[MAXN+1][MAXN+1];
int dp[MAXMASK][MAXN+1];

int cost( int mask, int k )
{
  if( dp[mask][k]==-1 )
  {
    dp[mask][k]=INF;

    for( auto it:g[k] )
      if( mask&(1<<it) )
        if( it!=0 || mask==(1<<k)+1 )
        {
          int c=cost(mask^(1<<k),it);

          if( c+weight[it][k]<dp[mask][k] )
            dp[mask][k]=c+weight[it][k];
        }
  }

  return dp[mask][k];
}

int main()
{
  cin>>n>>m;

  for( int i=1;i<=m;i++ )
  {
    int x, y, w; cin>>x>>y>>w;

    g[y].pb(x);
    weight[x][y]=w;
  }

  for( int j=0;j<(1<<n);j++ )
    for( int i=0;i<n;i++ )
      dp[j][i]=-1;

  dp[1][0]=0;

  int ans=INF;

  for( auto it:g[0] )
  {
    int c=cost((1<<n)-1,it);

    if( c+weight[it][0]<ans )
      ans=c+weight[it][0];
  }

  if( ans==INF )
    cout<<"Nu exista solutie";
  else
    cout<<ans;

  return 0;
}