#include <bits/stdc++.h>
using namespace std;
struct fast_ios {
  fast_ios() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  };
} fast_ios_;
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (auto &x : v) is >> x;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, vector<T> &v) {
  for (long long i = 0; i < v.size(); i++) {
    cout << v[i];
    if (i != v.size() - 1) cout << endl;
  };
  return os;
}
template <typename T1, typename T2>
ostream &operator<<(ostream &os, pair<T1, T2> p) {
  cout << '(' << p.first << ',' << p.second << ')';
  return os;
}
template <typename T>
void Out(T x) {
  cout << x << endl;
}
template <typename T1, typename T2>
void Ans(bool first, T1 y, T2 n) {
  if (first)
    Out(y);
  else
    Out(n);
}
using vec = vector<long long>;
using mat = vector<vec>;
using Pii = pair<long long, long long>;
using PiP = pair<long long, Pii>;
using PPi = pair<Pii, long long>;
using Pdi = pair<double, long long>;
using bools = vector<bool>;
using pairs = vector<Pii>;
const long long mod = 1000000007;
signed main() {
  long long N, M;
  cin >> N >> M;
  mat cost(N, vec(N, 0));
  long long ans = 0;
  for (long long i = (0); i < (M); i++) {
    long long a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    cost[a][b] = cost[b][a] = c;
    ans += c;
  }
  vec S((1LL << (N)), 0);
  for (long long i = (0); i < ((1LL << (N))); i++) {
    for (long long j = (0); j < (N); j++)
      for (long long k = (0); k < (j); k++)
        if ((i >> j) & (i >> k) & 1) S[i] += cost[j][k];
  }
  mat dp((1LL << (N)), vec(N, 0));
  for (long long i = (0); i < ((1LL << (N - 1))); i++)
    if (i & 1) dp[i][0] = S[i];
  for (long long now = (0); now < ((1LL << (N))); now++) {
    long long rest = ((1LL << (N)) - 1) ^ now;
    if (!(now & (rest >> (N - 1)) & 1)) continue;
    for (long long a = (0); a < (N); a++)
      if ((now >> a) & 1) {
        long long sub = rest;
        do {
          if ((sub >> (N - 1)) & 1) {
            if (cost[a][N - 1])
              dp[now | sub][N - 1] = max(dp[now | sub][N - 1],
                                         dp[now][a] + cost[a][N - 1] + S[sub]);
          } else {
            for (long long b = (0); b < (N); b++)
              if ((sub >> b) & 1) {
                if (cost[a][b])
                  dp[now | sub][b] =
                      max(dp[now | sub][b], dp[now][a] + cost[a][b] + S[sub]);
              }
          }
          sub = (sub - 1) & rest;
        } while (sub != rest);
      }
  }
  ans -= dp[(1LL << (N)) - 1][N - 1];
  Out(ans);
  return 0;
}
