#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

typedef vector<vector<pair<int, int>>> Graph;

const int oo = 0x3f3f3f3f;
const char ERROR[] = "Nu exista solutie";

inline
void update_(const Graph& graph, vector<vector<int>>& T, int mask, int node) {
  for (auto adj : graph[node]) {
          if (mask & (1 << adj.first)) {
            T[mask][node] = min(T[mask][node],
                T[mask ^ (1 << node)][adj.first] + adj.second);
          }
        }
}

int hamilton(const Graph& graph) {
  vector<vector<int>> T(1 << graph.size(), vector<int>(graph.size(), oo));

  T[1][0] = 0;
  for (int mask = 2; mask < (int) T.size(); ++mask) {
    for (int node = 0; node < (int) graph.size(); ++node) {
      if (mask & (1 << node)) {
        update_(graph, T, mask, node);
      }
    }
  }

  int full = (1 << graph.size()) - 1;
  int ans = oo;
  for (auto adj : graph[0]) {
    ans = min(ans, T[full][adj.first] + adj.second);
  }
  return ans;
}

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

  int n, m;
  fin >> n >> m;
  graph.resize(n);

  for (int e = 0; e < m; ++e) {
    int x, y, cost;
    fin >> x >> y >> cost;

    graph[y].push_back({x, cost});
  }

  int ans = hamilton(graph);
  if (ans == oo) {
    fout << ERROR << "\n";
  } else {
    fout << ans << "\n";
  }

  return 0;
}