#include <bits/stdc++.h>
using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const long long INF = 1LL << 29;
const long long mod = 1e9 + 7;
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  int n = v.size();
  for (int(i) = 0; (i) < (long long)(n); ++(i))
    os << v[i] << (i == n - 1 ? "" : " ");
  return os;
}
long long dp2[1 << 15], dp[1 << 15][15];
long long n, m, g[15][15];
int main() {
  cin >> n >> m;
  long long sum = 0;
  for (int(i) = 0; (i) < (long long)(m); ++(i)) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    g[a][b] = g[b][a] = c;
    sum += c;
  }
  dp2[0] = 0;
  for (int(i) = 0; (i) < (long long)(1 << n); ++(i)) {
    for (int(j) = 0; (j) < (long long)(n); ++(j)) {
      if ((i >> j) & 1) continue;
      long long w = 0;
      for (int(k) = 0; (k) < (long long)(n); ++(k)) {
        if ((i >> k) & 1) w += g[j][k];
      }
      dp2[i | (1 << j)] = dp2[i] + w;
    }
  }
  for (int(i) = 0; (i) < (long long)(1 << n); ++(i)) {
    if (i & 1) {
      dp[i][0] = dp2[i];
    }
  }
  for (int i = 1; i < 1 << n; i++) {
    if (!(i & 1)) continue;
    for (int j = (i - 1) & i; j > 0; j = (j - 1) & i) {
      if (!(j & 1)) continue;
      int j2 = i & (~j);
      for (int(k) = 0; (k) < (long long)(n); ++(k)) {
        if (!((j >> k) & 1)) continue;
        for (int(k2) = 0; (k2) < (long long)(n); ++(k2)) {
          if (!((j2 >> k2) & 1)) continue;
          if (g[k][k2])
            (dp[i][k2] = max(dp[i][k2], dp[j][k] + dp2[j2] + g[k][k2]));
        }
      }
    }
  }
  cout << sum - dp[(1 << n) - 1][n - 1] << endl;
  return 0;
}
