#include <bits/stdc++.h>
const int N = 17;
using namespace std;
int n, m, pw[N], sz, w[N][N], g[N][(1 << 17) + 5], h[(1 << 17) + 5],
    f[(1 << 17) + 5][N], ans, vis[(1 << 17) + 5], sum;
template <typename T>
inline T read() {
  T x = 0, w = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') w = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * w;
}
int lowbit(int x) { return x & (-x); }
int main() {
  n = read<int>(), m = read<int>();
  for (int i = (pw[0] = 1); i <= n; i++) pw[i] = 2 * pw[i - 1];
  for (int i = 0; i <= n; i++) vis[pw[i]] = i;
  sz = pw[n] - 1;
  for (int u, v, i = 1; i <= m; i++) {
    u = read<int>(), v = read<int>(), w[u][v] = w[v][u] = read<int>();
    sum += w[u][v], g[u][pw[v - 1]] = g[v][pw[u - 1]] = w[u][v];
  }
  for (int i = 1; i <= n; i++)
    for (int j = 0; j <= sz; j++)
      g[i][j] = g[i][lowbit(j)] + g[i][j ^ lowbit(j)];
  for (int u, v, i = 1; i <= sz; i++) {
    u = lowbit(i), v = i ^ u, u = vis[u] + 1;
    h[i] = h[v] + g[u][v];
  }
  memset(f, -0x3f, sizeof(f));
  for (int i = 1; i <= sz; i++)
    if (i & pw[0]) f[i][1] = h[i];
  for (int x, s = 1; s <= sz; s++)
    for (int i = 1; i <= n; i++)
      if (s & pw[i - 1]) {
        for (int j = 1; j <= n; j++)
          if (!(s & pw[j - 1]) && w[i][j]) {
            f[s | pw[j - 1]][j] = max(f[s | pw[j - 1]][j], f[s][i] + w[i][j]);
            x = sz ^ s;
          }
        for (int t = x; t; t = (t - 1) & x)
          f[s | t][i] = max(f[s | t][i], f[s][i] + h[t | pw[i - 1]]);
      }
  for (int i = 0; i <= sz; i++) ans = max(ans, f[i][n]);
  printf("%d\n", sum - ans);
  return 0;
}
