#include <bits/stdc++.h>
static const int MAXN = 15;
static const int INF = 0x7fffffff;
int n, m;
int g[MAXN][MAXN] = {{0}};
int f[1 << MAXN];
inline int calc_cut(int mask) {
  int ans = 0;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      if (g[i][j] > 0 && (mask & (1 << i)) && !(mask & (1 << j)))
        ans += g[i][j];
  return ans;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0, u, v, w; i < m; ++i) {
    scanf("%d%d%d", &u, &v, &w);
    --u, --v;
    g[u][v] = g[v][u] = w;
  }
  for (int i = 0; i < (1 << n); ++i) f[i] = calc_cut(i);
  int ans = INF;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < n; ++j)
      if (g[i][j] > 0) {
        for (int k = 0; k < (1 << n); ++k)
          if ((k & 1) && !(k & (1 << (n - 1))) && (k & (1 << i)) &&
              !(k & (1 << j))) {
            ans = std::min(ans, f[k] - g[i][j]);
          }
      }
  printf("%d\n", ans);
  return 0;
}
