#include <bits/stdc++.h>
#define maxn 18
#define inf INT_MAX / 2

using namespace std;

int ad[maxn+5][maxn+5];
int dp[(1<<maxn)+5][maxn];

int main ()
{
  ifstream fin ( "hamilton.in" );
  ofstream fout ( "hamilton.out" );

  int n, m;

  fin >> n >> m;

  int i, j, a, b, c;
  for ( i = 0; i < n; i++ )
    for ( j = 0; j < n; j++ )
      ad[i][j] = inf;

  for ( i = 0; i < m; i++ )
  {
    fin >> a >> b >> c;
    ad[a][b] = c;
  }

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

  int nod, conf, conn;
  for ( conf = 1; conf < (1<<n); conf++ )
    for ( nod = 1; nod < n; nod++ ) /// scot nod din conf
      if ( conf & (1<<nod) )
      {
        conn = conf - (1<<nod);
        for ( i = 0; i < n; i++ )
          if ( (conn & (1<<i)) && i != nod )
            dp[conf][nod] = min ( dp[conf][nod], dp[conn][i] + ad[i][nod] );
      }

  int _m = inf;
  for ( i = 1; i < n; i++ )
    if ( ad[i][0] < inf )
      _m = min ( _m, dp[(1<<n)-1][i] + ad[i][0] );

  if ( _m < inf )
    fout << _m;
  else
    fout << "Nu exista solutie";

  fin.close ();
  fout.close ();

  return 0;
}