#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int SIZE = 15;
int e[SIZE][SIZE];
int gg[1 << SIZE];
int dp[1 << SIZE][SIZE];
vector<int> d[1 << SIZE];
template <class T>
void maa(T& x, T y) {
  if (x < y) x = y;
}
template <class T>
void mii(T& x, T y) {
  if (x > y) x = y;
}
int main() {
  int sum = 0;
  int N, M;
  scanf("%d%d", &N, &M);
  for (int i = 0; i < (1 << N); ++i) {
    for (int j = 0; j < (N); ++j)
      if ((i >> j) & 1) d[i].push_back(j);
  }
  for (int i = 0; i < (M); ++i) {
    int x, y, v;
    scanf("%d%d%d", &x, &y, &v);
    sum += v;
    x--;
    y--;
    e[x][y] = e[y][x] = v;
    int ee = (1 << x) | (1 << y);
    for (int j = 0; j < (1 << N); ++j) {
      if ((j & ee) == ee) gg[j] += v;
    }
  }
  for (int i = 1; i < (1 << N); i += 2) {
    if (i + 1 != (1 << N)) dp[i][0] = gg[i];
    if (i != 1) {
      for (int j = (i - 2) & i;; j = (j - 2) & i) {
        for (auto x : d[j])
          for (auto y : d[i - j]) maa(dp[i][y], dp[j][x] + e[x][y] + gg[i - j]);
        if (j == 1) break;
      }
    }
  }
  int ma = 0;
  for (int i = (1); i < (N); ++i) maa(ma, dp[(1 << N) - 1][i]);
  printf("%d\n", sum - ma);
  return 0;
}
