#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
  if (a > b) {
    a = b;
    return true;
  } else
    return false;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
  if (a < b) {
    a = b;
    return true;
  } else
    return false;
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  long long N, M;
  cin >> N >> M;
  long long a[15][15] = {}, tot = 0;
  for (long long _ = (0); _ < ((M)); ++_) {
    long long x, y, c;
    cin >> x >> y >> c;
    a[x - 1][y - 1] = a[y - 1][x - 1] = c;
    tot += c;
  }
  vector<long long> sum(1 << N, 0);
  for (long long i = (0); i < ((1 << N)); ++i) {
    for (long long j = (0); j < ((N)); ++j) {
      if (!(i & (1LL << j))) continue;
      for (long long k = (0); k < ((j)); ++k) {
        if (!(i & (1LL << k))) continue;
        sum[i] += a[j][k];
      }
    }
  }
  vector<vector<long long>> dp(1 << N, vector<long long>(N, -(1LL << 60)));
  for (long long i = (0); i < ((1 << N)); ++i)
    if ((i & (1LL << 0))) dp[i][0] = sum[i];
  for (long long i = (0); i < ((1 << N)); ++i) {
    for (long long j = (0); j < ((N)); ++j) {
      long long mask = (1 << N) - 1 - i;
      for (long long k = mask; k >= 0; k--) {
        k &= mask;
        for (long long nx = (0); nx < ((N)); ++nx) {
          if (!(k & (1LL << nx)) || !a[j][nx]) continue;
          chmax(dp[i | k][nx], dp[i][j] + sum[k] + a[j][nx]);
        }
      }
    }
  }
  cout << tot - dp[(1 << N) - 1][N - 1] << endl;
  return 0;
}
