#include <bits/stdc++.h>
using namespace std;
vector<vector<int> > g;
int cs[512][512][4];
const int MN = 17;
const int SH = 8;
int am[MN][MN];
int n;
const int MSK = 1 << 15;
const int HL = (1 << SH) - 1;
void pre() {
  memset(cs, 0, sizeof(cs));
  for (int fm = 0; fm <= HL; fm++) {
    for (int sm = 0; sm <= HL; sm++) {
      for (int id = 0; id < 4; id++) {
        long long a = fm, b = sm;
        if (id & 2) {
          a <<= SH;
        }
        if (id & 1) {
          b <<= SH;
        }
        for (int i = 0; i < n; i++) {
          if (!((1 << i) & a)) continue;
          for (int j = 0; j < n; j++) {
            if (!((1 << j) & b)) continue;
            cs[fm][sm][id] += am[i][j];
          }
        }
      }
    }
  }
}
long long calc(int a, int b) {
  long long res = 0;
  for (int i = 0; i < 4; i++) {
    int fm = a, sm = b;
    if (i & 2) {
      fm >>= SH;
    } else {
      fm &= HL;
    }
    if (i & 1) {
      sm >>= SH;
    } else {
      sm &= HL;
    }
    res += cs[fm][sm][i];
  }
  return res;
}
long long dp[1 << MN][MN];
long long ds(int ms, int u) {
  if (dp[ms][u] != -1) return dp[ms][u];
  if (u == 0) {
    return ms == 1 ? 0 : 1e12;
  }
  if (ms == 0) return 1e12;
  long long ma = 1e12;
  for (int i = 0; i < g[u].size(); i++) {
    int v = g[u][i];
    if (!(ms & (1 << v))) continue;
    int nm = ms & (~(1 << u));
    ma = min(ma, ds(nm, v) + calc(nm & (~(1 << v)), 1 << u));
  }
  int mm = (1 << MN);
  while (1) {
    mm--;
    mm &= (ms & (~(1 << u)));
    if (mm <= 0) break;
    ma = min(ma, ds(ms ^ mm, u) + calc((ms ^ mm) & (~(1 << u)), mm));
  }
  return dp[ms][u] = ma;
}
int main() {
  int m;
  scanf("%d %d", &n, &m);
  memset(am, 0, sizeof(am));
  memset(dp, -1, sizeof(dp));
  g.assign(n, vector<int>());
  for (int i = 0; i < m; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    a--;
    b--;
    am[a][b] = am[b][a] = c;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  pre();
  printf("%lld\n", ds((1 << n) - 1, n - 1));
}
