#include <bits/stdc++.h>
using namespace std;
int N, M;
long long grp[16][16], gsum[1 << 16][16], dap[1 << 16];
vector<int> endp[555555];
vector<long long> val[555555];
int node_num(int chk, int ix) { return chk * N + ix; }
void make_edge(int s, int e, long long v) {
  endp[s].push_back(e);
  val[s].push_back(v);
}
void dfs(int ix, int pa, int pb, long long sum) {
  if (ix && (pa % 2 == 0 || ((1 << (N - 1)) & pa))) return;
  if (ix == N) {
    for (int i = 0; i < N; i++) {
      if ((pa & (1 << i)) == 0) continue;
      for (int j = 0; j < N; j++) {
        if ((pb & (1 << j)) == 0) continue;
        if (grp[i][j])
          make_edge(node_num(pa, i), node_num(pa + pb, j), sum - grp[i][j]);
      }
    }
    return;
  }
  dfs(ix + 1, pa, pb, sum);
  dfs(ix + 1, pa + (1 << ix), pb, sum + gsum[pb][ix]);
  dfs(ix + 1, pa, pb + (1 << ix), sum + gsum[pa][ix]);
}
int main() {
  scanf("%d%d", &N, &M);
  for (int i = 0; i < M; i++) {
    int a, b;
    long long v;
    scanf("%d%d%lld", &a, &b, &v), a--, b--;
    grp[a][b] = grp[b][a] = v;
  }
  for (int i = 0; i < (1 << N); i++) {
    for (int j = 0; j < N; j++) dap[node_num(i, j)] = 1ll << 50;
  }
  for (int i = 0; i < (1 << N); i++) {
    for (int j = 0; j < N; j++) {
      if (i & (1 << j)) continue;
      for (int k = 0; k < N; k++) {
        if ((i & (1 << k)) == 0) continue;
        gsum[i][j] += grp[k][j];
      }
    }
    if (i % 2 == 1 && ((1 << (N - 1)) & i) == 0)
      make_edge(0, node_num(i, 0), 0);
  }
  dfs(0, 0, 0, 0);
  dap[0] = 0;
  for (int i = 0; i < (1 << N) * N; i++) {
    for (int j = 0; j < endp[i].size(); j++) {
      int e = endp[i][j];
      long long v = val[i][j];
      if (dap[i] + v >= dap[e]) continue;
      dap[e] = dap[i] + v;
    }
  }
  printf("%lld\n", dap[node_num((1 << N) - 1, N - 1)]);
  return 0;
}
