#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <climits>
using namespace std;
typedef long long LL;

#ifdef INFOARENA
#define ProblemName "hamilton"
#endif

#define MCONCAT(A, B) A B
#ifdef ProblemName
#define InFile MCONCAT(ProblemName, ".in")
#define OuFile MCONCAT(ProblemName, ".out")
#else
#define InFile "fis.in"
#define OuFile "fis.out"
#endif

#define MUTATION_PERCENT 70
#define MAX_GENERATIONS 10000

const int MAXN = 18;
int N;
int M[MAXN][MAXN];
int dp[1 << MAXN][MAXN];
const int INFINIT = 10 * 1000000;

int main() {
  assert(freopen(InFile, "r", stdin));
  assert(freopen(OuFile, "w", stdout));
  int m;
  scanf("%d%d", &N, &m);
  if (N == 1) {
    puts("0");
    return 0;
  }
  for (int i = 0; i < N; ++i)
  for (int j = 0; j < N; ++j)
    M[i][j] = INFINIT;
  while (m--) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    M[a][b] = c;
  }
  int lm = 1 << N;
  dp[1][0] = 0;
  for (int msk = 2; msk < lm; ++msk) {
    dp[msk][0] = INFINIT;
    for (int i = 1; i < N; ++i) {
      int ibit = 1 << i;
      if (!(msk & ibit))
        continue;
      int pmask = msk ^ ibit;
      if (pmask == 0)
        continue;
      dp[msk][i] = INFINIT;
      for (int j = 0; j < N; ++j) {
        int jbit = 1 << j;
        if (!(pmask & jbit))
          continue;
        int cand = dp[pmask][j] + M[j][i];
        if (cand < dp[msk][i])
          dp[msk][i] = cand;
      }
    }
  }
  int best = INFINIT;
  for (int i = 1; i < N; ++i)
    best = min(best, dp[lm - 1][i] + M[i][0]);
  printf("%d\n", best);
  return 0;
}