#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline void cmin(T &x, const T &y) {
  if (y < x) x = y;
}
template <typename T>
inline void cmax(T &x, const T &y) {
  if (x < y) x = y;
}
inline int highbit(int x) {
  int res = 0;
  while (x) x -= (res = (x & (-x)));
  return res;
}
int n, m, sz, l2[1 << 15], dis[15][15];
long long f[1 << 15][15], g[1 << 15];
int main() {
  cin >> n >> m, sz = 1 << n;
  for (int i = 2; i < sz; ++i) l2[i] = l2[i / 2] + 1;
  long long sum = 0;
  for (int i = 1, u, v, w; i <= m; ++i)
    scanf("%d%d%d", &u, &v, &w), --u, --v, sum += dis[u][v] = dis[v][u] = w;
  for (int S = 1; S < sz; ++S)
    for (int i = 0; i < n; ++i)
      if ((S >> i) & 1)
        for (int j = i + 1; j < n; ++j)
          if ((S >> j) & 1) g[S] += dis[i][j];
  memset(f, -0x3f, sizeof f);
  long long ans = f[0][0];
  f[1][0] = 0;
  for (int S = 1; S < sz; ++S) {
    for (int Ss = S, i; Ss; Ss -= (Ss & (-Ss))) {
      i = l2[(Ss & (-Ss))];
      for (int T = (S - 1) & S; T; T = (T - 1) & S)
        if ((T >> i) & 1) cmax(f[S][i], f[(S ^ T) | (1 << i)][i] + g[T]);
      for (int j = 0; j < n; ++j)
        if (!((S >> j) & 1))
          if (dis[i][j]) cmax(f[S | (1 << j)][j], f[S][i] + dis[i][j]);
      if (i == n - 1) cmax(ans, f[S][i]);
    }
  }
  cout << sum - ans << endl;
  return 0;
}
