#include <bits/stdc++.h>
using namespace std;
const int MAXN = 15;
vector<pair<int, int> > g[MAXN + 1];
int dp[(1 << MAXN) + 1][MAXN + 1], delCost[(1 << MAXN) + 1];
void relax(int &x, int y) { x = max(x, y); }
int main() {
  int n, m;
  cin >> n >> m;
  int all = 0;
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    g[a].push_back({b, c});
    g[b].push_back({a, c});
    all += c;
  }
  for (int mask = 0; mask < (1 << n); mask++) {
    map<int, int> cur;
    for (int i = 1; i <= n; i++)
      if ((1 << (i - 1)) & mask) cur[i] = 1;
    int res = 0;
    for (int i = 1; i <= n; i++) {
      if (cur[i]) {
        for (auto u : g[i]) {
          if (cur[u.first]) res += u.second;
        }
      }
    }
    delCost[mask] = res / 2;
  }
  for (int i = 0; i < (1 << n); i++)
    for (int j = 0; j <= n; j++) dp[i][j] = -1;
  for (int mask = 1; mask < (1 << n); mask++) {
    if (!(mask & 1)) continue;
    dp[mask][1] = delCost[mask];
  }
  int ans = 0;
  for (int mask = 0; mask < (1 << n); mask++) {
    for (int submask = mask; submask; submask = (submask - 1) & mask) {
      int m1 = mask ^ submask;
      int m2 = submask;
      for (int v = 1; v <= n; v++) {
        if (!((1 << (v - 1)) & m2)) continue;
        for (auto u : g[v]) {
          if (!((1 << (u.first - 1)) & m1)) continue;
          if (dp[m1][u.first] == -1) continue;
          relax(dp[mask][v], dp[m1][u.first] + delCost[m2] + u.second);
        }
      }
    }
  }
  for (int mask = 0; mask < (1 << n); mask++) ans = max(ans, dp[mask][n]);
  cout << all - ans << "\n";
  return 0;
}
