#include <bits/stdc++.h>
using namespace std;
void fastIO() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
struct edge {
  int a, b, c;
  bool operator<(const edge &o) const { return c > o.c; }
};
const int MAXN = 15;
const int INF = 0x3f3f3f3f;
int n, m, c[MAXN][MAXN];
int dp[1 << MAXN][MAXN];
int f(int msk, int v) {
  int &ret = dp[msk][v];
  if (ret != -1) return ret;
  ret = -INF;
  msk ^= 1 << v;
  if (v == n - 1) {
    if (msk == 0)
      return ret = 0;
    else
      return ret = -INF;
  }
  for (int i = 0; i < (int)n; i++)
    if (c[v][i] && msk & (1 << i)) ret = max(ret, c[v][i] + f(msk, i));
  return ret;
}
int rep[MAXN], MSK;
vector<edge> E;
void init() {
  for (int i = 0; i < (int)n; i++) rep[i] = i;
}
int find(int v) {
  if (rep[v] == v) return v;
  return rep[v] = find(rep[v]);
}
bool can_unite(int v, int u) {
  v = find(v);
  u = find(u);
  if (v == u) return true;
  if (MSK & (1 << v) && MSK & (1 << u)) return false;
  return true;
}
void unite(int v, int u) {
  v = find(v);
  u = find(u);
  if (v == u) return;
  if (MSK & (1 << u)) swap(v, u);
  rep[u] = v;
}
int solve(int msk) {
  MSK = msk;
  init();
  int ret = 0;
  for (int i = 0; i < (int)E.size(); i++) {
    int v = E[i].a, u = E[i].b, cc = E[i].c;
    if (can_unite(v, u)) {
      unite(v, u);
    } else {
      ret += cc;
    }
  }
  ret -= dp[msk][0];
  return ret;
}
int main() {
  int ans = 0;
  scanf("%d", &n), scanf("%d", &m);
  for (int i = 0; i < (int)m; i++) {
    int a, b, cc;
    scanf("%d", &a), scanf("%d", &b);
    scanf("%d", &cc);
    a--;
    b--;
    c[a][b] = c[b][a] = cc;
    E.push_back({a, b, cc});
    ans += cc;
  }
  memset(dp, -1, sizeof(dp));
  for (int msk = 0; msk < (int)1 << n; msk++) {
    if (!(msk & 1) || !(msk & (1 << (n - 1)))) continue;
    f(msk, 0);
  }
  sort(E.begin(), E.end());
  for (int msk = 0; msk < (int)1 << n; msk++) {
    if (dp[msk][0] > -1) {
      ans = min(ans, solve(msk));
    }
  }
  printf("%d\n", ans);
}
