#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
const int Maxn = 16;
int dp[Maxn][Maxn][65537];
int n, m;
int dist[Maxn][Maxn];
int d2[Maxn][65537];
int go(int s, int t, int mask) {
  assert(mask >> t & 1);
  if (!(mask ^ (1 << s) ^ (1 << t))) {
    return dp[s][t][mask] = 0;
  }
  if (dp[s][t][mask] != -1) {
    return dp[s][t][mask];
  }
  int mask2 = mask ^ (1 << t);
  int ans = 1e9;
  while (mask2) {
    if ((mask2 >> s & 1) && !(mask2 >> t & 1)) {
      int cost = 0;
      for (int k = 0; k < n; k++) {
        if (mask2 >> k & 1) {
          cost += d2[k][mask ^ mask2];
        }
      }
      for (int k = 0; k < n; k++) {
        if ((mask2 >> k & 1) && k != s && k != t) {
          assert(mask >> k & 1);
          ans = min(ans, go(s, k, mask2) + go(k, t, mask ^ mask2 ^ (1 << k)) +
                             cost - d2[k][mask2]);
        }
      }
    }
    mask2 = (mask2 - 1) & mask;
  }
  return dp[s][t][mask] = ans;
}
int main() {
  for (int i = 0; i < Maxn; i++) {
    for (int j = 0; j < Maxn; j++) {
      for (int k = 0; k < 65537; k++) {
        dp[i][j][k] = -1;
      }
    }
  }
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    u--;
    v--;
    dist[u][v] = dist[v][u] = w;
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < (1 << n); j++) {
      for (int k = 0; k < n; k++) {
        if (j >> k & 1) {
          d2[i][j] += dist[i][k];
        }
      }
    }
  }
  printf("%d\n", go(0, n - 1, (1 << n) - 1));
}
