#include <stdio.h>
#include <vector>

static inline int min(int a, int b) {
  return a < b ? a : b;
}

#define MAXN 18
#define INFINIT 1000000000

int mat[MAXN][MAXN], dp[1 << MAXN][MAXN];
std::vector<int> grev[MAXN];

int main() {
  int n, m, i, u, v, w, mask, j, ans;
  
  #ifndef LOCAL
    freopen("hamilton.in", "r", stdin);
    freopen("hamilton.out", "w", stdout);
  #endif
  
  scanf("%d%d", &n, &m);
  for(i = 0; i < m; i++) {
    scanf("%d%d%d", &u, &v, &w);
    grev[v].push_back(u);
    mat[u][v] = w;
  }
  
  for(mask = 0; mask < (1 << n); mask++) {
    for(i = 0; i < n; i++) {
      dp[mask][i] = INFINIT;
    }
  }
  dp[1][0] = 0;
  
  for(mask = 1; mask < (1 << n); mask++) {
    for(i = 0; i < n; i++) {
      if(mask & (1 << i)) {
        for(j = 0; j < (int)grev[i].size(); j++) {
          if(mask & (1 << grev[i][j])) {
            dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << i)][grev[i][j]] + mat[grev[i][j]][i]);
          }
        }
      }
    }
  }
  
  ans = INFINIT;
  for(i = 1; i < n; i++) {
    if(mat[i][0] > 0) {
      ans = min(ans, dp[(1 << n) - 1][i] + mat[i][0]);
    }
  }
  printf("%d\n", ans);
  
  return 0;
}