#include <bits/stdc++.h>

using namespace std;

#define oo 0x3f3f3f3f

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

int n, m;
int dp[1 << 18][20];
vector<int> graph[20];
int C[20][20];

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

int dfs(int conf, int node) {
  if(dp[conf][node] == -1) {

    dp[conf][node] = oo;
    for(const auto& ngh : graph[node]) {
      if(!(conf & (1 << ngh))) {
        continue;
      }

      if(ngh == 0 && conf != 1 + (1 << node)) {
        continue;
      }

      dp[conf][node] = min(dp[conf][node], dfs(conf ^ (1 << node), ngh) + C[node][ngh]);
    }
  }
  return dp[conf][node];
}

void solve() {
  memset(dp, -1, sizeof(dp));

  dp[1][0] = 0;
  int result = oo;

  for(const int& node : graph[0]) {
    result = min(result, dfs((1 << n) - 1, node) + C[0][node]);
  }
  if(result == oo) {
    g<<"Nu exista solutie";
    return;
  }
  g<<result;
}

int main() {
  read();
  solve();

  return 0;
}