#include <bits/stdc++.h>
using namespace std;
vector<int> a[20];
int cc[20][20], all, n;
int mem[20][1 << 15];
vector<int> cst[1 << 15], cst1[1 << 15], cst2[1 << 15], cst3[1 << 15];
int dp(int x, int msk) {
  if (x == n - 1) return 0;
  if (mem[x][msk] != -1) {
    return mem[x][msk];
  }
  int res = -1e9, comp = ((1 << n) - 1) ^ msk;
  for (int i = 0; i < cst2[msk].size(); ++i) {
    res = max(res, cst3[msk][i] + dp(x, msk | cst2[msk][i]));
  }
  for (int i = 0; i < a[x].size(); ++i) {
    if ((1 << a[x][i]) & msk) continue;
    res = max(res, cc[x][a[x][i]] + dp(a[x][i], msk | (1 << a[x][i])));
  }
  mem[x][msk] = res;
  return res;
}
vector<pair<int, pair<int, int> > > v2;
vector<int> bits[1 << 15];
int sm[1 << 15][15], xx[1 << 15], v[1 << 15];
int main() {
  int m, x, y, c;
  cin >> n >> m;
  all = 0;
  for (int i = 0; i < m; ++i) {
    scanf("%d%d%d", &x, &y, &c);
    --x;
    --y;
    cc[x][y] = c;
    cc[y][x] = c;
    a[x].push_back(y);
    a[y].push_back(x);
    all += c;
  }
  int comp, tmp, jj, sum;
  for (int i = 1; i < (1 << n); ++i) {
    for (int j = 0; j < n; ++j) {
      if (i & (1 << j)) {
        bits[i].push_back(j);
        for (int k = 0; k < n; ++k) {
          sm[i][k] += cc[j][k];
        }
      }
    }
  }
  int cnt = 0, sz;
  for (int i = 1; i < (1 << n); ++i) {
    sum = 0;
    for (int j = 0; j < bits[i].size(); ++j) {
      for (int k = j + 1; k < bits[i].size(); ++k) {
        sum += cc[bits[i][j]][bits[i][k]];
      }
    }
    comp = ((1 << n) - 1) ^ i;
    jj = 0;
    sz = 0;
    for (int j = comp; j; j = (j - 1) & comp) {
      v[sz++] = j;
    }
    reverse(v, v + sz);
    for (int j = 0; j < sz; ++j) {
      jj = (v[j] - 1) & v[j];
      tmp = v[j] ^ jj;
      tmp = bits[tmp][0];
      cst[i].push_back(v[j]);
      if (j > 0) {
        cst1[i].push_back(max(cst1[i][xx[jj]], sum + sm[i][tmp]));
      } else {
        cst1[i].push_back(sum + sm[i][tmp]);
      }
      xx[v[j]] = j;
    }
  }
  for (int i = 1; i < (1 << n); ++i) {
    for (int j = 0; j < cst[i].size(); ++j) {
      cst2[cst[i][j]].push_back(i);
      cst3[cst[i][j]].push_back(cst1[i][j]);
    }
  }
  memset(mem, -1, sizeof mem);
  cout << all - dp(0, 1) << endl;
  return 0;
}
