#include <bits/stdc++.h>
using namespace std;
const int N = 16;
const int M = 300;
const int inf = 0x3f3f3f3f;
template <typename T>
inline bool chkmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
inline void read(T &x) {
  x = 0;
  int _f(0);
  char ch = getchar();
  while (!isdigit(ch)) _f |= (ch == '-'), ch = getchar();
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
  x = _f ? -x : x;
}
inline void file() {}
int n, m, tot, dp[N][1 << N], ans;
int c[N], w[N][1 << N], can[1 << N];
int q[1 << N], cnt;
int main() {
  file();
  int x, y, z;
  read(n), read(m);
  for (int i = 1, iE = m; i <= iE; ++i) {
    read(x), read(y), read(z);
    c[x] |= (1 << (y - 1));
    w[x][1 << (y - 1)] = z;
    c[y] |= (1 << (x - 1));
    w[y][1 << (x - 1)] = z;
    ans += z;
  }
  for (int i = 1, iE = n; i <= iE; ++i) {
    cnt = 0;
    for (int x = c[i]; x; x = (x - 1) & c[i]) q[++cnt] = x;
    for (int j = cnt, jE = 1; j >= jE; --j) {
      int x = q[j];
      w[i][x] = w[i][x ^ (x & -x)] + w[i][(x & -x)];
    }
  }
  memset(dp, -inf, sizeof(dp));
  dp[1][1] = 0;
  tot = (1 << n) - 1;
  for (int x = 1, xE = tot; x <= xE; ++x) {
    for (int u = 1, uE = n; u <= uE; ++u)
      if (x & (1 << (u - 1))) can[x] += w[u][x & c[u]];
    can[x] >>= 1;
  }
  long long MAX = 0;
  for (int x = 1, xE = tot; x <= xE; ++x)
    for (int u = 1, uE = n; u <= uE; ++u)
      if (dp[u][x] >= 0) {
        int bx = tot ^ x;
        for (int sm = bx; sm; sm = (sm - 1) & bx)
          chkmax(dp[u][x | sm], dp[u][x] + can[sm | (1 << (u - 1))]);
        for (int v = 1, vE = n; v <= vE; ++v)
          if (c[u] & (1 << (v - 1)) && !(x & (1 << (v - 1))))
            chkmax(dp[v][x | (1 << (v - 1))], dp[u][x] + w[v][1 << (u - 1)]);
      }
  printf("%d\n", ans - dp[n][tot]);
  return 0;
}
