#include <bits/stdc++.h>
#define oo 0x3f3f3f3f

using namespace std;
ifstream f("hamilton.in");
ofstream g("hamilton.out");
int n, m;
int cost[20][20], dp[1 << 18][20];
vector<int> graf[20];

void read()
{
  f>>n>>m;
  int x, y;
  for(int i = 1;i <= m;++i)
    f>>x>>y, graf[y].push_back(x), f>>cost[x][y];
}

int recur(int conf, int node)
{
  if(dp[conf][node] == -1)
  {
    dp[conf][node] = oo;

    for(int vecin : graf[node])
      if((1 << vecin) & conf)
      {
        if(vecin == 0 && conf != 1 + (1 << node)) continue;

        dp[conf][node] = min(dp[conf][node], recur(conf ^ (1 << node), vecin) + cost[vecin][node]);
      }
  }

  return dp[conf][node];
}

void solve()
{
  memset(dp, -1, sizeof(dp));
  int result = oo;
  dp[1][0] = 0;

  for(int vecin: graf[0])
    result = min(result, recur((1 << n) - 1, vecin) + cost[vecin][0]);
  
  if(result < oo)
    g<<result;
  else
    g<<"Nu exista solutie";
}

int main()
{
  read();
  solve();
  return 0;
}