#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<pair<long long, long long> > g[100];
int sum[1 << 16];
int dp[1 << 16][17];
int tot = 0;
int main() {
  cin >> n >> m;
  for (long long i = (long long)(0); i < (long long)(m); i++) {
    int a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    g[a].push_back(pair<long long, long long>(b, c));
    g[b].push_back(pair<long long, long long>(a, c));
    tot += c;
  }
  for (long long S = (long long)(0); S < (long long)(1 << n); S++) {
    for (long long i = (long long)(0); i < (long long)(n); i++) {
      if (!((S >> i) & 1)) continue;
      for (pair<long long, long long> p : g[i]) {
        if ((S >> p.first) & 1) sum[S] += p.second;
      }
    }
    sum[S] /= 2;
  }
  for (long long i = (long long)(0); i < (long long)(1 << n); i++)
    for (long long j = (long long)(0); j < (long long)(n); j++)
      dp[i][j] = -INT_MAX;
  dp[0][0] = 0;
  for (long long S = (long long)(0); S < (long long)(1 << n); S++)
    for (long long i = (long long)(0); i < (long long)(n); i++) {
      if (dp[S][i] == -INT_MAX) continue;
      long long S_ = ((1 << n) - 1) ^ S;
      for (long long T = S_; T >= 0; T--) {
        T &= S_;
        dp[S | T][i] = (dp[S | T][i] > dp[S][i] + sum[T] ? dp[S | T][i]
                                                         : dp[S][i] + sum[T]);
        for (pair<long long, long long> p : g[i]) {
          if (((T >> p.first) & 1) || ((S >> p.first) & 1)) continue;
          dp[S | T | (1 << i)][p.first] =
              (dp[S | T | (1 << i)][p.first] > dp[S][i] + sum[T] + p.second
                   ? dp[S | T | (1 << i)][p.first]
                   : dp[S][i] + sum[T] + p.second);
        }
      }
    }
  int res = -INT_MAX;
  for (long long S = (long long)(0); S < (long long)(1 << n); S++)
    res = (res > dp[S][n - 1] ? res : dp[S][n - 1]);
  cout << tot - res << endl;
  return 0;
}
