#include <bits/stdc++.h>
using namespace std;
const int maxn = 20;
const int maxm = 100005;
int e[maxn][maxn], n, m, bin[maxn];
long long dp[maxn][1 << 15];
long long cs[maxn][1 << 15];
long long cst[1 << 15], sum;
void upd(long long &x, long long y) {
  if (x < y) x = y;
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 0; i < n; i++) bin[1 << i] = i;
  for (int u, v, w, i = 1; i <= m; i++)
    scanf("%d %d %d", &u, &v, &w), u--, v--, e[u][v] = e[v][u] = w, sum += w;
  for (int i = 0; i < n; i++)
    for (int j = 1; j < (1 << n); j++)
      cs[j][i] = cs[j ^ (j & -j)][i] + e[bin[j & -j]][i];
  for (int i = 1; i < (1 << n); i++)
    cst[i] = cst[i ^ (i & -i)] + cs[i ^ (i & -i)][bin[i & -i]];
  memset(dp, -1, sizeof dp);
  dp[1][0] = 0;
  for (int s = 0; s < (1 << n); s++)
    for (int u = 0; u < n; u++)
      if ((s >> u & 1) && dp[s][u] != -1) {
        for (int t = 0; t < n; t++)
          if (!(s >> t & 1) && e[u][t])
            upd(dp[s ^ (1 << t)][t], e[u][t] + dp[s][u]);
        int o = ((1 << n) - 1) ^ s;
        for (int t = o; t; t = t - 1 & o)
          upd(dp[s ^ t][u], dp[s][u] + cst[t] + cs[t][u]);
      }
  printf("%lld", sum - dp[(1 << n) - 1][n - 1]);
  return 0;
}
