#include <bits/stdc++.h>
using namespace std;
const int nsz = 15, msksz = (1 << nsz) - 1, inf = 0x3f3f3f3f;
int n, m, to, sum, id[msksz + 5], g[nsz + 5][nsz + 5];
int dp[msksz + 5][nsz + 5], ts[msksz + 5][nsz + 5], s[msksz + 5], ans;
map<pair<int, int>, int> mx;
void inline link(int u, int v, int w) { g[u][v] = g[v][u] = w; }
string inline str(int S) {
  string s;
  for (int i = 0; i < n; ++i) {
    s += ((S >> i) & 1) + 48;
  }
  return s;
}
void inline init() {
  for (int i = 0; i < n; ++i) {
    id[1 << i] = i;
  }
}
void inline upd(int &a, int b) { a < b && (a = b); }
int inline qry(int S1, int S2) { return mx[make_pair(S1, S2)]; }
int main() {
  freopen("dat.in", "r", stdin);
  freopen("dat.out", "w", stdout);
  ios::sync_with_stdio(0);
  cin >> n >> m;
  init();
  to = (1 << n) - 1;
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    --u, --v;
    link(u, v, w);
    sum += w;
  }
  for (int S = 0; S <= to; ++S) {
    int sum = 0;
    for (int t = S, d1 = t & -t; d1; t -= d1, d1 = t & -t) {
      int u = id[d1];
      for (int t = S, d2 = t & -t; d2; t -= d2, d2 = t & -t) {
        int v = id[d2];
        sum += (u < v) * g[u][v];
      }
    }
    s[S] = sum;
  }
  for (int S = 0; S <= to; ++S) {
    int rS = to ^ S;
    for (int t = rS, d2 = t & -t; d2; t -= d2, d2 = t & -t) {
      int u = id[d2], sum = 0;
      for (int t = S, d1 = t & -t; d1; t -= d1, d1 = t & -t) {
        int v = id[d1];
        sum += g[u][v];
      }
      ts[S][u] = sum;
    }
  }
  for (int S = 0; S <= to; ++S) {
    int rS = to ^ S;
    for (int tS = rS; tS; tS = rS & (tS - 1)) {
      int w = 0;
      for (int t = S, d1 = t & -t; d1; t -= d1, d1 = t & -t) {
        int u = id[d1];
        upd(w, ts[tS][u]);
      }
      mx[make_pair(S, tS)] = w;
    }
  }
  memset(dp, -inf, sizeof(dp));
  dp[1][0] = 0;
  for (int S = 0; S <= to; ++S) {
    if (!(S & 1)) continue;
    int rS = to ^ S;
    for (int tS = rS; tS; tS = rS & (tS - 1)) {
      if ((tS >> (n - 1)) & 1) continue;
      int mx = qry(S, tS);
      for (int t = S, d = t & -t; d; t -= d, d = t & -t) {
        int u = id[d];
        upd(dp[S | tS][u], dp[S][u] + mx + s[tS]);
      }
    }
    for (int t = S, d1 = t & -t; d1; t -= d1, d1 = t & -t) {
      int u = id[d1];
      for (int t = rS, d2 = t & -t; d2; t -= d2, d2 = t & -t) {
        int v = id[d2];
        if (!g[u][v]) continue;
        if (v == 0) continue;
        upd(dp[S | (1 << v)][v], dp[S][u] + g[u][v]);
      }
    }
  }
  for (int S = 0; S <= to; ++S) {
    upd(ans, dp[S][n - 1]);
  }
  cerr << sum << ' ' << ans << '\n';
  cout << sum - ans << '\n';
  cerr << sum - ans << '\n';
}
