#include <bits/stdc++.h>
namespace Not_Sure {
inline void check_min(int a, int &b) {
  if (a < b) b = a;
}
inline void check_max(int a, int &b) {
  if (a > b) b = a;
}
const int N = 17, M = N * N * 2, INF = 2147483647;
inline bool inset(int S, int p) { return S & (1 << (p - 1)); }
int begin[N], next[M], to[M], w[M];
int f[N][1 << N];
int n, m, e, S;
void add(int x, int y, int z, bool k = 1) {
  to[++e] = y;
  next[e] = begin[x];
  begin[x] = e;
  w[e] = z;
  if (k) add(y, x, z, 0);
}
void initialize() {
  scanf("%d%d", &n, &m);
  S = 1 << n;
  for (int i = 1, u, v, k; i <= m; i++)
    scanf("%d%d%d", &u, &v, &k), add(u, v, k);
  for (int i = 0; i < S; i++)
    for (int j = 1; j <= n; j++) f[j][i] = INF;
}
int val[N], v[1 << N];
void get_val(int k) {
  memset(val, 0, sizeof(val));
  for (int p = 1; p <= n; p++)
    if (!inset(k, p))
      for (int i = begin[p]; i; i = next[i])
        if (inset(k, to[i])) val[p] += w[i];
}
int lowbit(int x) { return x & (-x); }
int bit(int x) {
  int ret = 0;
  while (x) x >>= 1, ret++;
  return ret;
}
int calc(int nk, int T) {
  if (1 || nk == T) {
    int ret = 0, tmp = nk;
    for (int i = 1; i <= n; i++)
      if (inset(nk, i)) ret += val[i];
    return v[tmp] = ret;
  } else {
    int h = lowbit(T ^ nk);
    return v[nk] = v[nk | h] - val[bit(h)];
  }
}
void solve() {
  initialize();
  int T = (S - 1) ^ 1, g, cost, sum;
  f[1][1] = 0;
  for (int k = T; k; k = (k - 1) & T) f[1][k | 1] = 0;
  for (int i = 1; i <= n; i++)
    for (int k = 0; k < S; k++) {
      if (f[i][k] == INF) continue;
      int dk = (S - 1) ^ k;
      get_val(k);
      for (int u = begin[i], j; u; u = next[u]) {
        j = to[u];
        if (inset(k, j)) continue;
        sum = 0;
        for (int o = begin[j]; o; o = next[o])
          if (inset(k, to[o])) sum += w[o];
        sum -= w[u];
        T = dk ^ (g = 1 << (j - 1));
        check_min(f[i][k] + sum, f[j][k | g]);
        for (int nk = T; nk; nk = (nk - 1) & T) {
          cost = calc(nk, T) + sum;
          check_min(f[i][k] + cost, f[j][k | nk | g]);
        }
      }
    }
  printf("%d\n", f[n][S - 1]);
}
}  // namespace Not_Sure
int main() {
  Not_Sure::solve();
  return 0;
}
