#include <bits/stdc++.h>
using namespace std;
const long long INF = (long long)1e9 + 5;
const long long MOD = (long long)1e9 + 7;
const int MAXN = 15;
int n, m;
long long dp[1 << MAXN][MAXN], G[MAXN][MAXN], prof[1 << MAXN], sum;
int forbid(int x) { return ((1 << n) - 1) ^ 1 << x; }
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    G[a][b] = G[b][a] = c;
    sum += c;
  }
  for (int i = 0; i < (1 << n); i++) {
    for (int j = 0; j < n; j++) {
      for (int k = j + 1; k < n; k++) {
        if ((i >> j & 1) && (i >> k & 1)) {
          prof[i] += G[j][k];
        }
      }
    }
  }
  int t = n - 1;
  for (int i = 0; i < (1 << n); i++) {
    dp[i][t] = prof[i];
  }
  for (int i = 0; i < (1 << n); i++) {
    if (~i >> t & 1) continue;
    for (int a = 0; a < t; a++) {
      if (~i >> a & 1) continue;
      for (int b = 0; b < n; b++) {
        if ((~i >> b & 1) || a == b || G[a][b] == 0) continue;
        int tot = i & forbid(a) & forbid(b) & forbid(t), sub = tot;
        while (1) {
          int take = sub | 1 << a;
          dp[i][a] = max(dp[i][a], dp[i ^ take][b] + prof[take] + G[a][b]);
          if (sub == 0) break;
          sub = (sub - 1) & tot;
        }
      }
    }
  }
  cout << sum - dp[(1 << n) - 1][0] << '\n';
  return 0;
}
