#include <bits/stdc++.h>
using namespace std;
const int maxn = 17, maxst = (1 << 17) - 1;
int n, m, sum, e[maxn][maxn], p[maxst], f[maxst][maxn];
inline int max(int x, int y) { return x < y ? y : x; }
inline void up(int &x, int y) { x = max(x, y); }
int main() {
  scanf("%d%d", &n, &m);
  int a, b, c, ans = 0;
  memset(f, -1, sizeof(f));
  for (int i = 0; i < m; ++i) {
    scanf("%d%d%d", &a, &b, &c);
    --a;
    --b;
    e[a][b] = e[b][a] = c;
    sum += c;
  }
  for (int i = 0; i < 1 << n; ++i) {
    for (int j = 0; j < n; ++j)
      if (i & (1 << j))
        for (int k = 0; k < n; ++k)
          if (i & (1 << k)) p[i] += e[j][k];
    p[i] >>= 1;
  }
  f[1][0] = 0;
  for (int i = 1; i < (1 << n); ++i) {
    for (int j = 0; j < n; ++j) {
      if (f[i][j] == -1) continue;
      for (int k = 0; k < n; ++k) {
        if (i & (1 << k)) continue;
        if (e[j][k] == 0) continue;
        up(f[i | (1 << k)][k], f[i][j] + e[j][k]);
      }
      int revi = (((1 << n) - 1) ^ i) | (1 << j);
      for (int k = revi; k; k = (k - 1) & revi) up(f[i | k][j], f[i][j] + p[k]);
    }
  }
  for (int i = 0; i < (1 << n); ++i) up(ans, f[i][n - 1]);
  printf("%d\n", sum - ans);
  return 0;
}
