#include <fstream>

using namespace std;

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

constexpr int N = 18;
constexpr int LIM = 1 << N;
constexpr int INF = 1e9;

int dp[LIM][N];
int cost[N][N];

int n, m;

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

  fill(cost[0], cost[0] + N * N, INF);
    //cost[i][i] = 0;

  for (int i = 0 ; i < m; i++)
  {
    int x, y, c;
    in>>x>>y>>c;
    cost[x][y] = c;
  }

  int lim = 1 << n;
  fill(dp[0], dp[0] + N * LIM, INF);

  dp[1][0] = 0;

  for (int mask = 1; mask < lim; mask += 2)
  {
    for(int node = 0; node < n; node++)
    {
      if((1 << node) & mask)
      {
        for(int succ = 0; succ < n; succ++)
        {
          if(!((1 << succ) & mask) && cost[node][succ] != INF)
          {
            int newMask = mask | (1 << succ);
            dp[newMask][succ] = min(dp[newMask][succ], dp[mask][node] + cost[node][succ]);
          }
        }
      }
    }
  }

  int mask = (1 << n) - 1;
  int res = INF;
  for (int j = 1; j < n; j++)
  {
    if (cost[j][0] == INF) continue;
    res = min(res, dp[mask][j] + cost[j][0]);
  }

  if(res == INF)
  {
    out<<"Nu exista solutie";
  }
  else out<<res;
}