#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
const int MAXN = 15;
int n, m;
int e[MAXN][MAXN];
int sum[1 << MAXN];
int mem[1 << MAXN][MAXN];
int go(int left, int at) {
  if (at == n - 1) return sum[left];
  int &ret = mem[left][at];
  if (ret == -1) {
    ret = INT_MIN;
    for (int to = (0); to < (n); ++to)
      if (left & (1 << to))
        if (e[at][to] != -1) {
          int mask = (1 << n) - 1 - (left - (1 << to));
          for (int g = 0; g < (1 << n); g = (g + mask + 1) & ~mask) {
            int cur = go(left - (1 << to) - g, to);
            if (cur == INT_MIN) continue;
            cur += sum[(1 << to) + g];
            cur += e[at][to];
            if (cur > ret) {
              ret = cur;
            }
          }
        }
  }
  return ret;
}
void run() {
  scanf("%d%d", &n, &m);
  for (int i = (0); i < (n); ++i)
    for (int j = (0); j < (n); ++j) e[i][j] = -1;
  for (int i = (0); i < (m); ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    --a, --b;
    e[a][b] = e[b][a] = c;
  }
  for (int i = (0); i < (1 << n); ++i) {
    sum[i] = 0;
    for (int j = (0); j < (n); ++j)
      for (int k = (j + 1); k < (n); ++k)
        if ((i & (1 << j)) && (i & (1 << k)) && (e[j][k] != -1))
          sum[i] += e[j][k];
  }
  memset(mem, -1, sizeof(mem));
  int keep = go((1 << n) - 1 - (1 << 0), 0);
  int tot = 0;
  for (int i = (0); i < (n); ++i)
    for (int j = (i + 1); j < (n); ++j)
      if (e[i][j] != -1) tot += e[i][j];
  int ret = tot - keep;
  printf("%d\n", ret);
}
int main() {
  run();
  return 0;
}
