#include <bits/stdc++.h>
using namespace std;
const int N = 20, M = 33005, inf = 0x3F3F3F3F;
int n, m, ec[N][N], ans = inf, U;
int dp[M][N], sc[N][M], g[M];
bool ok[N][M];
int find(int* fa, int x) { return fa[x] == x ? x : fa[x] = find(fa, fa[x]); }
bool judge(int u, int S) {
  if (S >> u & 1) return -1;
  static int fa[N];
  static bool vi[N], ok[N];
  for (int i = 0; i < n; i++) fa[i] = i, vi[i] = ok[i] = 0;
  for (int i = 0; i < n; i++)
    if (S >> i & 1)
      for (int j = i + 1; j < n; j++)
        if (S >> j & 1) fa[find(fa, i)] = find(fa, j);
  for (int i = 0; i < n; i++)
    if (S >> i & 1) {
      int k = find(fa, i);
      vi[k] = true;
      if (!ec[u][i]) continue;
      ok[k] = true;
    }
  for (int i = 0; i < n; i++)
    if (vi[i] && !ok[i]) return false;
  return true;
}
inline void upd(int& x, int y) { x < y ?: x = y; }
inline int F(int S, int T) {
  int res = 0;
  for (int i = 0; i < n; i++)
    if (T >> i & 1) res += sc[S][i];
  return res;
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, u, v, c; i <= m; i++)
    scanf("%d%d%d", &u, &v, &c), u--, v--, ec[u][v] = ec[v][u] = c;
  U = (1 << n) - 1;
  for (int i = 0; i < n; i++)
    for (int j = 0; j <= U; j++) ok[i][j] = judge(i, j);
  for (int S = 0; S <= U; S++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (S >> j & 1) sc[S][i] += ec[i][j];
  memset(dp, 0x3F, sizeof(dp));
  for (int S = 1; S <= U; S += 2)
    if (ok[0][S ^ 1]) dp[S][0] = 0;
  for (int S = 0; S <= U / 2; S++)
    for (int u = 0; u < n; u++)
      if (dp[S][u] != inf) {
        for (int K = U - S, T = K; T; T = (T - 1) & K) g[T] = F(S, T);
        for (int v = 0; v < n; v++)
          if (~S >> v & 1) {
            if (!ec[u][v]) continue;
            int T = U - S - (1 << v), cur = sc[S ^ (1 << u)][v];
            for (int z = T; z; z = (z - 1) & T)
              if (ok[v][z]) upd(dp[S | 1 << v | z][v], dp[S][u] + cur + g[z]);
            upd(dp[S | 1 << v][v], dp[S][u] + cur);
          }
      }
  for (int S = U / 2 + 1; S <= U; S++)
    if (dp[S][n - 1] != inf) upd(ans, dp[S][n - 1] + F(S, U ^ S));
  printf("%d\n", ans);
  return 0;
}
