#include <bits/stdc++.h>
using namespace std;
int n, m, a, b, c;
int cost[15 + 100][15 + 100], dep[(1 << 15) + 100][15 + 3];
int sum[15 + 3][(1 << 15) + 100];
vector<int> ve[(1 << 15) + 100];
int dp(int mask, int tadi) {
  if (tadi == n - 1 && mask == (1 << n) - 1) return 0;
  int &ret = dep[mask][tadi];
  if (ret != -1) return ret;
  ret = 1e9;
  for (int i = 0; i < n; i++) {
    if (mask & (1 << i) || cost[tadi][i] == 0) continue;
    if (mask == 9 && tadi == 3) {
      cout << "i"
           << " = " << (i) << endl;
      cout << "sum[i][mask ^ (1 << tadi)]"
           << " = " << (sum[i][mask ^ (1 << tadi)]) << endl;
    }
    ret = min(ret, dp(mask | (1 << i), i) + sum[i][mask ^ (1 << tadi)]);
  }
  int inv = 1 << n;
  inv -= mask + 1;
  int idx = -1;
  for (int i = inv; i > 0; i = (i - 1) & inv) {
    idx += 1;
    ret = min(ret, dp(mask | i, tadi) + ve[mask][idx] - sum[tadi][i]);
    if (mask == 9 && tadi == 3) {
    }
  }
  return ret;
}
int main() {
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    cin >> a >> b >> c;
    a -= 1;
    b -= 1;
    cost[a][b] = cost[b][a] = c;
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 1 << n; j++) {
      for (int k = 0; k < n; k++) {
        if (j & (1 << k)) sum[i][j] += cost[i][k];
      }
    }
  }
  for (int i = 0; i < 1 << n; i++) {
    int inv = 1 << n;
    inv -= i + 1;
    int idx = -1;
    for (int j = inv; j > 0; j = (j - 1) & inv) {
      idx += 1;
      int tot = 0;
      for (int k = 0; k < n; k++) {
        if (j & (1 << k)) tot += sum[k][i];
      }
      ve[i].push_back(tot);
    }
  }
  memset(dep, -1, sizeof dep);
  ;
  cout << dp(1, 0) << endl;
}
