#include <bits/stdc++.h>
using namespace std;
template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()) {
  v.assign(a, vector<T>(b, t));
}
template <class F, class T>
void convert(const F &f, T &t) {
  stringstream ss;
  ss << f;
  ss >> t;
}
void mainmain() {
  int n, m;
  cin >> n >> m;
  vector<vector<int> > vv;
  initvv(vv, n, n);
  int ans = 0;
  for (int(i) = (0); (i) < ((m)); ++(i)) {
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;
    vv[a][b] = vv[b][a] = c;
    ans += c;
  }
  vector<vector<int> > sum;
  initvv(sum, n, 1 << n);
  for (int(i) = (0); (i) < ((n)); ++(i)) {
    for (int(j) = (0); (j) < ((1 << n)); ++(j)) {
      if (j & (1 << i))
        ;
      else
        continue;
      int t = 0;
      for (int(k) = (0); (k) < ((n)); ++(k)) {
        for (int(l) = (0); (l) < ((k)); ++(l)) {
          if (j & (1 << k) && j & (1 << l)) {
            t += vv[k][l];
          }
        }
      }
      sum[i][j] = t;
    }
  }
  vector<vector<int> > dp;
  initvv(dp, n, 1 << n, -0x3f3f3f3f);
  dp[0][1] = 0;
  for (int(i) = (0); (i) < ((n)); ++(i)) {
    for (int(j) = (0); (j) < ((1 << n)); ++(j)) {
      if (j & (1 << i))
        ;
      else
        continue;
      for (int(k) = (0); (k) < ((n)); ++(k)) {
        if (j & (1 << k)) continue;
        if (vv[i][k] == 0) continue;
        dp[k][j + (1 << k)] = max(dp[k][j + (1 << k)], dp[i][j] + vv[i][k]);
      }
      int mask = (1 << n) - 1;
      mask ^= j;
      for (int k = mask; k; k = (k - 1) & mask) {
        if (j & k) continue;
        dp[i][j + k] = max(dp[i][j + k], dp[i][j] + sum[i][k + (1 << i)]);
      }
    }
  }
  cout << ans - dp[n - 1][(1 << n) - 1] << endl;
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20);
  mainmain();
}
