import sys readline = sys.stdin.readline N,M = map(int,readline().split()) G = [{} for i in range(N)] for _ in range(M): a,b,c = map(int,readline().split()) a -= 1 b -= 1 if b in G[a]: if G[a][b] < c: G[a][b] = c G[b][a] = c else: G[a][b] = c G[b][a] = c # 一筆書きなので、端点からしか線を引けない。 # dp[L][R][S] = 頂点の集合がSで端点がLとRである場合の最大距離 dp = [[[-1] * (1 << N) for i in range(N)] for j in range(N)] for i in range(N): dp[i][i][1 << i] = 0 ans = 0 for status in range(1 << N): for L in range(N): for R in range(L, N): if dp[L][R][status] == -1: continue # Lから出ている線を延長する場合 for v, dist in G[L].items(): if (status >> v) & 1: continue next_status = status | (1 << v) if dp[v][R][next_status] < dp[L][R][status] + dist: dp[v][R][next_status] = dp[L][R][status] + dist if ans < dp[v][R][next_status]: ans = dp[v][R][next_status] # L < Rの場合は、Rからの端点も延長を試す for v, dist in G[R].items(): if (status >> v) & 1: continue next_status = status | (1 << v) if dp[L][v][next_status] < dp[L][R][status] + dist: dp[L][v][next_status] = dp[L][R][status] + dist if ans < dp[L][v][next_status]: ans = dp[L][v][next_status] print(ans)