#include <bits/stdc++.h>
using namespace std;
template <typename T>
ostream& operator<<(ostream& s, const vector<T>& v) {
  int len = v.size();
  s << "\n";
  for (int i = 0; i < len; ++i) {
    s << v[i];
    if (i < len - 1) s << "\t";
  }
  s << "\n";
  return s;
}
template <typename T>
ostream& operator<<(ostream& s, const vector<vector<T> >& vv) {
  int len = vv.size();
  for (int i = 0; i < len; ++i) {
    s << vv[i];
  }
  return s;
}
template <class T>
using vv = vector<vector<T> >;
struct UF {
  vector<int> par;
  vector<int> sizes;
  UF(int n) : par(n), sizes(n, 1) {
    for (int i = 0; i < n; ++i) {
      par[i] = i;
    }
  }
  int root(int x) {
    if (x == par[x]) {
      return x;
    }
    return par[x] = root(par[x]);
  }
  void unite(int x, int y) {
    x = root(x);
    y = root(y);
    if (x == y) {
      return;
    }
    if (sizes[x] < sizes[y]) {
      swap(x, y);
    }
    par[y] = x;
    sizes[x] += sizes[y];
    sizes[y] = 0;
  }
  bool same(int x, int y) { return root(x) == root(y); }
  int size(int x) { return sizes[root(x)]; }
};
int n, m;
vector<vector<int> > g;
vector<int> pre_cost;
vector<bool> pre_calculated;
void calculate_pre_cost(int s) {
  if (pre_calculated[s]) {
    return;
  }
  for (int(i) = (0); (i) < (n); ++(i)) {
    if ((s >> i) % 2 == 1) {
      continue;
    }
    int add_cost = 0;
    for (int(j) = (0); (j) < (n); ++(j)) {
      if ((s >> j) % 2 == 1) {
        add_cost += g[i][j];
      }
    }
    if (s != 0 && add_cost == 0) {
      continue;
    }
    int next_s = s + (1 << i);
    pre_cost[next_s] = pre_cost[s] + add_cost;
    calculate_pre_cost(next_s);
  }
  pre_calculated[s] = true;
  return;
}
void search() {}
int main() {
  scanf("%d %d", &n, &m);
  g.assign(n, vector<int>(n, 0));
  int cost_all = 0;
  for (int(i) = (0); (i) < (m); ++(i)) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    a -= 1;
    b -= 1;
    g[a][b] = c;
    g[b][a] = c;
    cost_all += c;
  }
  pre_cost.assign((1 << n), -1);
  pre_cost[0] = 0;
  pre_calculated.assign((1 << n), false);
  calculate_pre_cost(0);
  vector<vector<int> > dp;
  deque<vector<int> > stk;
  stk.push_back(vector<int>{1, 0, 0});
  dp.assign((1 << n), vector<int>(n, 0));
  while (!stk.empty()) {
    vector<int> state = stk.front();
    stk.pop_front();
    if (state[2] < dp[state[0]][state[1]]) {
      continue;
    }
    dp[state[0]][state[1]] = state[2];
    for (int(add_x) = (0); (add_x) < (n); ++(add_x)) {
      if ((state[0] >> add_x) % 2 == 1) {
        continue;
      }
      if (g[state[1]][add_x] == 0) {
        continue;
      }
      for (int(t) = (0); (t) < ((1 << n)); ++(t)) {
        if ((t >> add_x) % 2 == 0) {
          continue;
        }
        bool continue_flag = false;
        for (int(i) = (0); (i) < (n); ++(i)) {
          if ((t >> i) % 2 == 0) {
            continue;
          }
          if ((state[0] >> i) % 2 == 1) {
            continue_flag = true;
            break;
          }
        }
        if (continue_flag) {
          continue;
        }
        if (pre_cost[t] == -1) {
          continue;
        }
        stk.push_back(vector<int>{
            state[0] + t, add_x,
            dp[state[0]][state[1]] + g[state[1]][add_x] + pre_cost[t]});
      }
    }
  }
  printf("%d\n", cost_all - dp[(1 << n) - 1][n - 1]);
  return 0;
}
