#include <bits/stdc++.h>
using namespace std;
const int inf = (1 << 30);
struct edge {
  int to, c;
  edge() {}
  edge(int to, int c) : to(to), c(c) {}
};
int N, M, dp[15][1 << 15];
bool v[15][1 << 15];
vector<edge> g[15];
int calc(int nod, int mask);
int gen(int k, int omask, int nmask, int st, int tot) {
  if (k == N) {
    int res = inf;
    if (st == N - 1) {
      if (nmask == (1 << N) - 1) return 0;
      return inf;
    }
    for (edge e : g[st])
      if ((nmask & (1 << e.to)) == 0)
        res = min(res, tot - e.c + calc(e.to, nmask));
    return res;
  }
  int v1 = 0, v2 = 0;
  for (edge e : g[k]) {
    if (e.to > k) continue;
    if ((omask & (1 << e.to)) == 0 && (nmask & (1 << e.to))) v1 += e.c;
    if ((nmask & (1 << e.to)) == 0) v2 += e.c;
  }
  if (k == st)
    return gen(k + 1, omask, nmask | (1 << k), st, tot + v2);
  else if (k == N - 1)
    return gen(k + 1, omask, nmask, st, tot + v1);
  else {
    int res = gen(k + 1, omask, nmask, st, tot + v1);
    res = min(res, gen(k + 1, omask, nmask | (1 << k), st, tot + v2));
    return res;
  }
}
int calc(int nod, int mask) {
  if (v[nod][mask]) return dp[nod][mask];
  v[nod][mask] = 1;
  dp[nod][mask] = gen(0, mask, mask, nod, 0);
  return dp[nod][mask];
}
int main() {
  cin >> N >> M;
  int i, x, y, c;
  for (i = 1; i <= M; i++) {
    cin >> x >> y >> c;
    x--, y--;
    g[x].push_back(edge(y, c));
    g[y].push_back(edge(x, c));
  }
  cout << calc(0, 0) << "\n";
  return 0;
}
