#include <bits/stdc++.h>
using namespace std;
const int N = 20, M = N * N, K = 1 << 16, inf = 1e9;
int n, m, nm, i, j, k, x, p[K], v[K], f[N][K], mx[N];
int et, he[N], sum;
struct edge {
  int l, to, v;
} e[M];
void gmax(int &x, int k) {
  if (k > x) x = k;
}
int main() {
  scanf("%d%d", &n, &m);
  nm = 1 << n;
  for (i = 1; i <= m; i++) {
    int x, y, v;
    scanf("%d%d%d", &x, &y, &v);
    sum += v;
    e[++et].l = he[x];
    he[x] = et;
    e[et].to = y;
    e[et].v = v;
    e[++et].l = he[y];
    he[y] = et;
    e[et].to = x;
    e[et].v = v;
  }
  for (i = 1; i <= n; i++) p[1 << i - 1] = i;
  for (i = 1; i < nm; i++) {
    int x = p[i & -i];
    v[i] = v[i - (i & -i)];
    for (j = he[x]; j; j = e[j].l)
      if ((i >> e[j].to - 1) & 1) v[i] += e[j].v;
  }
  for (x = 1; x <= n; x++)
    for (i = 0; i < nm; i++) f[x][i] = -inf;
  f[1][1] = 0;
  for (i = 1; i < nm - 1; i++) {
    for (x = 1; x <= n; x++) mx[x] = -inf;
    for (x = 1; x <= n; x++) {
      if (f[x][i] == -inf) continue;
      for (j = he[x]; j; j = e[j].l) gmax(mx[e[j].to], f[x][i] + e[j].v);
    }
    for (j = i; j < nm; j = (j + 1) | i)
      for (k = j ^ i; k; k -= k & -k) {
        int x = p[k & -k];
        gmax(f[x][j], mx[x] + v[j ^ i]);
      }
  }
  printf("%d", sum - f[n][nm - 1]);
}
