#include <bits/stdc++.h>
using namespace std;
int N, M, a[114], b[114], c[114], p[114], par[19], sum[32777];
int root(int x) {
  if (x == par[x]) return x;
  return par[x] = root(par[x]);
}
int main() {
  cin >> N >> M;
  int all_cost = 0;
  for (int i = 0; i < M; i++) {
    cin >> a[i] >> b[i] >> c[i];
    a[i]--, b[i]--;
    sum[(1 << a[i]) + (1 << b[i])] += c[i];
    all_cost += c[i];
  }
  for (int i = 0; i < M; i++) {
    for (int j = i + 1; j < M; j++) {
      if (c[i] < c[j]) {
        swap(a[i], a[j]);
        swap(b[i], b[j]);
        swap(c[i], c[j]);
      }
    }
  }
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 1 << N; j++) {
      if (!(j & (1 << i))) {
        sum[j + (1 << i)] += sum[j];
      }
    }
  }
  int ret = 0;
  for (int i = 0; i < 1 << N; i++) {
    if ((i & 1) && (i & (1 << (N - 1)))) {
      for (int j = 0; j < N; j++) par[j] = j;
      int tre = 0;
      for (int j = 0; j < M; j++) {
        if ((a[j] & i) && (b[j] & i) && root(a[j]) != root(b[j])) {
          tre += c[j];
          par[root(a[j])] = root(b[j]);
        }
      }
      int sub = 0;
      int sp = ((1 << N) - i - 1);
      for (int j = sp; j >= 0; j--) {
        j &= sp;
        sub = max(sub, sum[j + 1] + sum[sp - j + (1 << (N - 1))]);
      }
      ret = max(ret, tre + sub);
    }
  }
  cout << all_cost - ret << endl;
  return 0;
}
