#include <bits/stdc++.h>
using namespace std;
int read() {
  int x = 0;
  bool fu = 0;
  char ch = 0;
  while (ch > '9' || ch < '0') {
    ch = getchar();
    if (ch == '-') fu = 1;
  }
  while (ch <= '9' && ch >= '0') x = (x * 10 + ch - 48), ch = getchar();
  return fu ? -x : x;
}
int n, m, tot, t1, t2, g[17][17], full[1 << 16], dp[17][1 << 16];
void dfs(int pos, int S, int now, int t) {
  if ((t == n)) {
    dp[pos][S | now] =
        max(dp[pos][S | now], dp[pos][S] + full[(1 << pos) | now]);
    return;
  }
  if ((S & (1 << t))) {
    dfs(pos, S, now, t + 1);
    return;
  }
  dfs(pos, S, now, t + 1);
  dfs(pos, S, now | (1 << t), t + 1);
}
int main() {
  memset(dp, -0x3f, sizeof(dp));
  dp[0][1] = 0;
  cin >> n >> m;
  for (register int i = 1, iend = m; i <= iend; ++i) {
    cin >> t1 >> t2;
    t1--, t2--;
    cin >> g[t2][t1];
    tot += g[t2][t1];
    g[t1][t2] = g[t2][t1];
  }
  for (register int i = 1; i < (1 << n); i++) {
    for (register int j = 1; j < n; j++) {
      if (i & (1 << j)) {
        for (register int k = 0; k < j; k++) {
          if (i & (1 << k)) {
            full[i] += g[j][k];
          }
        }
      }
    }
  }
  for (register int i = 0; i < n; i++) {
    for (register int S = ((1 << i) | 1); S < (1 << n); S += 2) {
      for (register int j = 1; j < n; j++) {
        if (!g[i][j] || (S & (1 << j))) continue;
        dp[j][S | (1 << j)] = max(dp[j][S | (1 << j)], dp[i][S] + g[i][j]);
      }
      dfs(i, S, 0, 0);
    }
  }
  cout << tot - dp[n - 1][(1 << n) - 1];
  return 0;
}
