#include <bits/stdc++.h>
using namespace std;
int N, M, adjm[20][20], par[20], dp[33005][16], vis[33005][16], cost[33005],
    dp2[33005][16], vis2[33005][16];
vector<pair<int, pair<int, int> > > edgelist;
vector<int> nodes;
int fp(int x) {
  if (par[x] == x)
    return x;
  else
    return par[x] = fp(par[x]);
}
void merge(int x, int y) {
  x = fp(x);
  y = fp(y);
  par[x] = y;
}
int f(int bm, int x, int c) {
  if (vis[bm][x] == c)
    return dp[bm][x];
  else
    vis[bm][x] = c;
  if (bm == 1 && x == 0)
    return 0;
  else if (!(bm & (1 << x)))
    return -500000000;
  int mx = -500000000;
  for (int i = 0; i < N; i++) {
    if (bm & (1 << i)) {
      mx = max(mx, f(bm ^ (1 << x), i, c) + adjm[i][x]);
    }
  }
  return dp[bm][x] = mx;
}
int f2(int bm, int v, int c, int bleft) {
  if (vis2[bm][v] == c)
    return dp2[bm][v];
  else
    vis2[bm][v] = c;
  if (v == 0 && bm == 0)
    return 0;
  else if (v == 0)
    return -500000000;
  bleft ^= (1 << nodes[v - 1]);
  bool allowed[N];
  memset(allowed, 0, sizeof(allowed));
  for (int i = 0; i < N; i++) {
    if (bm & (1 << i)) allowed[i] = 1;
  }
  for (int i = 0; i < N; i++) {
    if (bleft & (1 << i)) allowed[i] = 0;
  }
  vector<int> allowed_bits;
  int mx = -500000000;
  for (int i = 0; i < N; i++)
    if (allowed[i] && i != nodes[v - 1]) allowed_bits.push_back(i);
  for (int i = 0; i < (1 << allowed_bits.size()); i++) {
    int b = (1 << nodes[v - 1]);
    for (int j = 0; j < allowed_bits.size(); j++)
      if (i & (1 << j)) b ^= (1 << allowed_bits[j]);
    mx = max(mx, f2(bm ^ b, v - 1, c, bleft) + cost[b]);
  }
  return dp2[bm][v] = mx;
}
int main() {
  scanf("%d%d", &N, &M);
  int total = 0;
  memset(adjm, -63, sizeof(adjm));
  for (int i = 0; i < M; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    a--;
    b--;
    edgelist.push_back(make_pair(c, make_pair(a, b)));
    total += c;
    adjm[a][b] = adjm[b][a] = c;
  }
  sort(edgelist.begin(), edgelist.end(),
       greater<pair<int, pair<int, int> > >());
  for (int i = 0; i < (1 << N); i++) {
    for (int j = 0; j < edgelist.size(); j++) {
      int a = edgelist[j].second.first, b = edgelist[j].second.second,
          c = edgelist[j].first;
      if ((i & (1 << a)) && (i & (1 << b))) cost[i] += c;
    }
  }
  int ans = 0;
  memset(vis, -1, sizeof(vis));
  memset(vis2, -1, sizeof(vis2));
  for (int i = 0; i < (1 << N); i++) {
    if (!(i & 1) || !(i & (1 << (N - 1)))) continue;
    nodes.clear();
    int cans = 0;
    for (int j = 0; j < N; j++)
      if (i & (1 << j)) nodes.push_back(j);
    cans += f2((1 << N) - 1, nodes.size(), i, i);
    ans = max(ans, cans + f(i, N - 1, i));
  }
  printf("%d\n", total - ans);
}
