#include <bits/stdc++.h>
using namespace std;
const long long MAX = 17;
const int INF = 0x3f3f3f3f;
long long n, m, conn[MAX][MAX], dist[MAX][MAX], dp[MAX][1 << MAX],
    visit[MAX][1 << MAX], calc[1 << MAX], trk[MAX], ans;
void calc_build(long long first, long long v, long long idx) {
  if (idx >= n) {
    calc[first] = v;
    return;
  }
  calc_build(first, v, idx + 1);
  trk[idx] = 1;
  for (long long i = 0; i < idx; i++)
    if (trk[i]) v += dist[i][idx];
  calc_build(first + (1 << idx), v, idx + 1);
  trk[idx] = 0;
}
long long dp_build(long long first, long long bit) {
  if (first == n - 1) return dp[first][bit] = calc[bit];
  if (visit[first][bit] == 0) {
    long long cmp[MAX], cmp_cnt = 0;
    visit[first][bit] = 1;
    for (long long i = 0; i < n; i++)
      if (((1 << i) & bit) && conn[i][first]) {
        long long cmp[MAX], cmp_cnt = 0;
        for (long long j = 0; j < n - 1; j++)
          if (((1 << j) & bit) && i != j && first != j) cmp[cmp_cnt++] = j;
        for (long long j = 0; j < (1 << (cmp_cnt)); j++) {
          long long g1 = 1 << first, g2;
          for (long long k = 0; k < cmp_cnt; k++)
            if ((1 << k) & j) g1 += (1 << cmp[k]);
          g2 = bit - g1;
          dp[first][bit] =
              max(dp[first][bit], calc[g1] + dp_build(i, g2) + dist[first][i]);
        }
      }
  }
  return dp[first][bit];
}
int main() {
  scanf("%lld%lld", &n, &m);
  for (long long i = 0; i < m; i++) {
    long long t1, t2, t;
    scanf("%lld%lld%lld", &t1, &t2, &t);
    t1--, t2--;
    conn[t1][t2] = 1, dist[t1][t2] = t;
    conn[t2][t1] = 1, dist[t2][t1] = t;
    ans += t;
  }
  calc_build(0, 0, 0);
  printf("%lld\n", ans - dp_build(0, (1 << n) - 1));
}
