#include <bits/stdc++.h>
using namespace std;
const long long int MOD = 1000000007;
template <typename T, typename U>
istream &operator>>(istream &i, pair<T, U> &A) {
  i >> A.first >> A.second;
  return i;
}
template <typename T>
istream &operator>>(istream &i, vector<T> &A) {
  for (auto &I : A) {
    i >> I;
  }
  return i;
}
template <typename T, typename U>
ostream &operator<<(ostream &o, const pair<T, U> &A) {
  o << A.first << " " << A.second;
  return o;
}
template <typename T>
ostream &operator<<(ostream &o, const vector<T> &A) {
  int i = A.size();
  for (auto &I : A) {
    o << I << (--i ? " " : "");
  }
  return o;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long int N, M;
  cin >> N >> M;
  const int sz = 1 << N;
  vector<vector<int>> edge(N, vector<int>(N, 0));
  vector<vector<bool>> edge2(N, vector<bool>(N, false));
  long long int uku = 0;
  for (int i = 0; i < M; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    uku += c;
    a--;
    b--;
    edge[a][b] = c;
    edge[b][a] = c;
    edge2[a][b] = true;
    edge2[b][a] = true;
  }
  vector<long long int> sum(sz, 0);
  for (int i = 0; i < sz; i++) {
    for (int j = 0; j < N; j++) {
      for (int k = j + 1; k < N; k++) {
        if ((i >> j & 1) && (i >> k & 1)) {
          sum[i] += edge[j][k];
        }
      }
    }
  }
  const long long int INF = 1e15;
  const int msk = sz - 1;
  vector<vector<long long int>> dp(N, vector<long long int>(sz, -INF));
  for (int i = 1; i < sz; i += 2) {
    dp[0][i] = sum[i];
  }
  for (int i = 0; i < sz; i++) {
    int all = msk ^ i;
    for (int k = all; k > 0; k = (k - 1) & all) {
      assert((i & k) == 0);
      for (int u = 0; u < N; u++) {
        if ((i >> u & 1) == 0) {
          continue;
        }
        for (int v = 0; v < N; v++) {
          if ((k >> v & 1) && edge2[u][v]) {
            dp[v][i | k] = max(dp[v][i | k], dp[u][i] + sum[k] + edge[u][v]);
          }
        }
      }
    }
  }
  cout << uku - dp.back().back() << endl;
  return 0;
}
