#include <bits/stdc++.h>
long long dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
long long dy[8] = {1, 0, -1, 0, -1, 1, 1, -1};
using namespace std;
class pa3 {
 public:
  long long x;
  long long y, z;
  pa3(long long x = 0, long long y = 0, long long z = 0) : x(x), y(y), z(z) {}
  bool operator<(const pa3 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    return z < p.z;
  }
  bool operator>(const pa3 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    return z > p.z;
  }
  bool operator==(const pa3 &p) const {
    return x == p.x && y == p.y && z == p.z;
  }
  bool operator!=(const pa3 &p) const {
    return !(x == p.x && y == p.y && z == p.z);
  }
};
class pa4 {
 public:
  long long x;
  long long y, z, w;
  pa4(long long x = 0, long long y = 0, long long z = 0, long long w = 0)
      : x(x), y(y), z(z), w(w) {}
  bool operator<(const pa4 &p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    if (z != p.z) return z < p.z;
    return w < p.w;
  }
  bool operator>(const pa4 &p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    if (z != p.z) return z > p.z;
    return w > p.w;
  }
  bool operator==(const pa4 &p) const {
    return x == p.x && y == p.y && z == p.z && w == p.w;
  }
};
class pa2 {
 public:
  long long x, y;
  pa2(long long x = 0, long long y = 0) : x(x), y(y) {}
  pa2 operator+(pa2 p) { return pa2(x + p.x, y + p.y); }
  pa2 operator-(pa2 p) { return pa2(x - p.x, y - p.y); }
  bool operator<(const pa2 &p) const { return y != p.y ? y < p.y : x < p.x; }
  bool operator>(const pa2 &p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const pa2 &p) const {
    return abs(x - p.x) == 0 && abs(y - p.y) == 0;
  }
  bool operator!=(const pa2 &p) const {
    return !(abs(x - p.x) == 0 && abs(y - p.y) == 0);
  }
};
string itos(long long i) {
  ostringstream s;
  s << i;
  return s.str();
}
long long gcd(long long v, long long b) {
  if (v > b) return gcd(b, v);
  if (v == b) return b;
  if (b % v == 0) return v;
  return gcd(v, b % v);
}
double distans(double x1, double y1, double x2, double y2) {
  double rr = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
  return sqrt(rr);
}
long long mod;
long long extgcd(long long a, long long b, long long &x, long long &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
pair<long long, long long> operator+(const pair<long long, long long> &l,
                                     const pair<long long, long long> &r) {
  return {l.first + r.first, l.second + r.second};
}
long long pr[1000010];
long long inv[1000010];
long long beki(long long wa, long long rr, long long warukazu) {
  if (rr == 0) return 1 % warukazu;
  if (rr == 1) return wa % warukazu;
  wa %= warukazu;
  if (rr % 2 == 1)
    return ((long long)beki(wa, rr - 1, warukazu) * (long long)wa) % warukazu;
  long long zx = beki(wa, rr / 2, warukazu);
  return (zx * zx) % warukazu;
}
double bekid(double w, long long r) {
  if (r == 0) return 1.0;
  if (r == 1) return w;
  if (r % 2) return bekid(w, r - 1) * w;
  double f = bekid(w, r / 2);
  return f * f;
}
long long comb(long long nn, long long rr) {
  long long r = pr[nn] * inv[rr];
  r %= mod;
  r *= inv[nn - rr];
  r %= mod;
  return r;
}
void gya(long long ert) {
  pr[0] = 1;
  for (long long i = 1; i < ert; i++) {
    pr[i] = (pr[i - 1] * i) % mod;
  }
  for (long long i = 0; i < ert; i++) inv[i] = beki(pr[i], mod - 2, mod);
}
vector<pa3> ve;
long long g[1 << 15];
long long er[110][1 << 15] = {};
long long dp[1 << 15][15] = {};
bool sumi[1 << 15][15] = {};
long long eda[15][15];
long long n;
long long dfs(long long bit, long long las) {
  if (sumi[bit][las]) return dp[bit][las];
  long long ans = 0;
  for (long long i = bit; i > 0; i = ((i - 1) & bit)) {
    if (!(i & (1 << las))) continue;
    long long nokori = (i ^ bit);
    for (long long j = 0; j < n; j++)
      if (nokori & (1 << j))
        if (eda[las][j] >= 0) {
          ans = max(ans, dfs(nokori, j) + eda[las][j] + g[i]);
        }
  }
  sumi[bit][las] = 1;
  dp[bit][las] = ans;
  return ans;
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long m;
  cin >> n >> m;
  for (long long i = 0; i < n; i++)
    for (long long j = 0; j < n; j++) {
      eda[i][j] = -1000000007;
    }
  for (long long i = 0; i < m; i++) {
    long long y, yy, cc;
    cin >> y >> yy >> cc;
    y--;
    yy--;
    eda[y][yy] = cc;
    eda[yy][y] = cc;
    ve.push_back({y, yy, cc});
  }
  for (long long i = 0; i < m; i++) {
    for (long long j = 0; j < (1 << n); j++) {
      er[i + 1][j] = max(er[i + 1][j], er[i][j]);
      if (j & (1 << ve[i].x))
        if (j & (1 << ve[i].y)) {
          er[i + 1][j] = max(er[i + 1][j], er[i][j] + ve[i].z);
        }
    }
  }
  for (long long i = 0; i < (1 << n); i++) {
    g[i] = er[m][i];
  }
  for (long long i = 0; i < (1 << n); i++)
    if (i & 1)
      if (!(i & (1 << (n - 1)))) {
        sumi[i][0] = 1;
        dp[i][0] = g[i];
      }
  long long w = dfs((1 << n) - 1, n - 1);
  long long souwa = 0;
  for (auto v : ve) souwa += v.z;
  cout << souwa - w << endl;
  return 0;
}
