#include <bits/stdc++.h>
using namespace std;
int n, m;
int F[15][15];
int T[1 << 15];
int G[15][15];
int dp[15][1 << 15];
int DP[2][1 << 15];
int fp[1 << 15];
int gp[1 << 15];
int turn;
vector<int> sm[1 << 15];
int vis[15][1 << 15];
int tot = 0;
int dfs(int pos, int leave) {
  if (leave == 0) {
    return G[pos][n - 1];
  }
  if (vis[pos][leave] == turn) {
    return dp[pos][leave];
  }
  vis[pos][leave] = turn;
  dp[pos][leave] = -1;
  for (int i = 1; i < n; ++i) {
    if (leave >> (i - 1) & 1) {
      int nxt = dfs(i, leave - (1 << (i - 1)));
      if (nxt == -1) continue;
      dp[pos][leave] = max(dp[pos][leave], nxt + G[pos][i]);
    }
  }
  return dp[pos][leave];
}
int work(int o, int p) {
  vector<int> a;
  a.push_back(0);
  for (int i = 0; i < n - 2; ++i) {
    if (o >> i & 1) {
      a.push_back(i + 1);
    }
  }
  a.push_back(n - 1);
  for (auto &j : sm[p]) {
    DP[0][p - j] = T[j * 2 + 1];
  }
  int st = 0;
  for (int i = 1; i < a.size(); ++i) {
    st ^= 1;
    memset(DP[st], 0, sizeof(DP[st]));
    for (auto &j : sm[p]) {
      for (auto &k : sm[j]) {
        DP[st][j - k] =
            max(DP[st][j - k], DP[st ^ 1][j] + T[k * 2 + (1 << a[i])]);
      }
    }
  }
  return DP[st][0];
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i == j) continue;
      G[i][j] = -1;
    }
  }
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    u--;
    v--;
    tot += w;
    G[u][v] = max(G[u][v], w);
    G[v][u] = max(G[v][u], w);
    if (u > v) swap(u, v);
    F[u][v] += w;
  }
  for (int j = 0; j < (1 << n); ++j) {
    for (int i = 0; i < n; ++i) {
      if ((j >> i & 1) == 0) continue;
      for (int k = i + 1; k < n; ++k) {
        if (j >> k & 1) {
          T[j] += F[i][k];
        }
      }
    }
  }
  for (int i = 0; i < (1 << n); ++i) {
    for (int j = 0; j < (1 << n); ++j) {
      if ((j & i) == j) sm[i].push_back(j);
    }
  }
  memset(dp, -1, sizeof(dp));
  memset(vis, -1, sizeof(vis));
  for (int i = 0; i < (1 << (n - 2)); ++i) {
    turn = i;
    fp[i] = dfs(0, i);
  }
  int ret = (1 << (n - 2)) - 1;
  int ans = 0;
  for (int i = 0; i < (1 << (n - 2)); ++i) {
    if (fp[i] == -1) continue;
    ans = max(ans, fp[i] + work(i, ret - i));
  }
  cout << tot - ans << endl;
  return 0;
}
