#include <bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,popcnt")
using namespace std;
using ll = long long;
using ld = long double;
const int maxn = 1 << 17, mod = 1e9 + 7;
int n, m, p[17], dp[1 << 15], d[20][20], h[1 << 15][15], cl[1 << 15],
    f[1 << 15][15], pr[1 << 15], tot = 0;
void ret(int x) {
  cout << bitset<15>(x ^ pr[x]) << '\n';
  if (!pr[x]) return;
  ret(pr[x]);
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  p[0] = 1;
  cin >> n >> m;
  memset(d, -0x3f, sizeof d);
  for (int f, t, c, i = 0; i < m; i++) {
    cin >> f >> t >> c;
    --f, --t;
    d[f][t] = d[t][f] = c;
    tot += c;
  }
  for (int i = 0; i < 1 << n; i++) {
    for (int j = 0; j < n; j++) {
      for (int k = 0; k < n; k++) {
        if (i >> k & 1)
          if (d[j][k] >= 0) h[i][j] += d[j][k];
      }
    }
  }
  for (int i = 0; i < 1 << n; i++) {
    for (int j = 0; j < n; j++)
      if (i >> j & 1) {
        for (int k = 0; k < j; k++)
          if (i >> k & 1) {
            if (d[j][k] >= 0) cl[i] += d[j][k];
          }
      }
  }
  memset(f, -0x3f, sizeof f);
  memset(dp, -0x3f, sizeof dp);
  f[1][0] = 0;
  for (int i = 0; i < 1 << n; i++) {
    for (int j = 0; j < n; j++) {
      if (~i >> j & 1) continue;
      if ((i & 1) && j == n - 1) dp[i] = max(dp[i], f[i][j]);
      for (int k = 0; k < n; k++) {
        if (d[j][k] >= 0)
          if (~i >> k & 1)
            f[i | 1 << k][k] =
                max(f[i | 1 << k][k], f[i][j] - h[i][k] + 2 * d[j][k]);
      }
    }
  }
  for (int i = 0; i < 1 << n; i++) {
    int t = i;
    t ^= (1 << n) - 1;
    for (int j = t; j > 0; j = (j - 1) & t) {
      for (int k = 0; k < n; k++) {
        if (i >> k & 1) {
          dp[i | j] = max(dp[i | j], dp[i] + h[j][k] + cl[j]);
          if (dp[i | j] == dp[i] + h[j][k] + cl[j]) pr[i | j] = i;
        }
      }
    }
  }
  cout << tot - dp[(1 << n) - 1] << '\n';
  return 0;
}
