#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18; // folosit long long pentru cost mare

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

  int N, M;
  fin >> N >> M;

  vector<vector<long long>> mat(N, vector<long long>(N, -1));
  for (int i = 0; i < M; i++) {
    int x, y;
    long long c;
    fin >> x >> y >> c;
    mat[x][y] = c;
  }

  int start = 0; // putem alege nodul 0 ca start
  vector<vector<long long>> dp(1 << N, vector<long long>(N, INF));
  vector<vector<int>> parent(
      1 << N, vector<int>(N, -1)); // pentru reconstruirea drumului

  dp[1 << start][start] = 0;

  for (int mask = 0; mask < (1 << N); mask++) {
    for (int u = 0; u < N; u++) {
      if (!(mask & (1 << u)) || dp[mask][u] == INF)
        continue;
      for (int v = 0; v < N; v++) {
        if (mask & (1 << v))
          continue; // deja vizitat
        if (mat[u][v] == -1)
          continue; // nu există muchie
        if (dp[mask | (1 << v)][v] > dp[mask][u] + mat[u][v]) {
          dp[mask | (1 << v)][v] = dp[mask][u] + mat[u][v];
          parent[mask | (1 << v)][v] = u; // memorăm nodul anterior
        }
      }
    }
  }

  long long ans = INF;
  int last = -1;
  int full = (1 << N) - 1;
  for (int u = 0; u < N; u++) {
    if (mat[u][start] != -1 && dp[full][u] + mat[u][start] < ans) {
      ans = dp[full][u] + mat[u][start];
      last = u;
    }
  }

  if (ans == INF) {
    fout << "Nu exista solutie\n";
    return 0;
  }

  // reconstruim ciclul
  vector<int> cycle;
  int mask = full;
  while (last != -1) {
    cycle.push_back(last);
    int temp = parent[mask][last];
    mask ^= (1 << last);
    last = temp;
  }
  reverse(cycle.begin(), cycle.end());
  cycle.push_back(start); // închidem ciclul

  // afișăm costul
  fout << ans << "\n";

  // dacă vrei să afișezi și ciclul (opțional):
  // for (int x : cycle) fout << x << " ";
  // fout << "\n";

  return 0;
}