// This code is AI-generated. (AI 生成的代码)
// NOIP2017 宝藏: subset DP by "layers". dis[mask][v] = cheapest edge from v to
// any node in mask. dp[mask][k] = min cost to have explored mask with the
// deepest nodes on layer k; adding a layer T costs (k+1) * sum dis[mask][v].
#include <stdio.h>
typedef long long ll;
enum { N = 12, MAXM = 4096, INF = 0x3f3f3f3f };
static int d[N][N], dis[MAXM][N], dp[MAXM][N + 1];
static char buf[1 << 16], ob[64];
static char *gp;
static inline int rd() {
while (*gp < '0' && *gp != '-') gp++;
int neg = (*gp == '-'); if (neg) gp++;
int v = 0; while (*gp >= '0' && *gp <= '9') v = v * 10 + (*gp++ - '0');
return neg ? -v : v;
}
int main() {
int len = (int)fread(buf, 1, sizeof(buf) - 1, stdin);
buf[len] = 0; gp = buf;
int n = rd(), m = rd();
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) d[i][j] = INF;
for (int i = 0; i < m; i++) {
int u = rd() - 1, v = rd() - 1, w = rd();
if (w < d[u][v]) d[u][v] = d[v][u] = w;
}
int full = (1 << n) - 1;
for (int mask = 1; mask <= full; mask++) {
int low = mask & -mask, u = __builtin_ctz(low), rest = mask ^ low;
for (int v = 0; v < n; v++) {
int a = rest ? dis[rest][v] : INF;
int b = d[v][u];
dis[mask][v] = a < b ? a : b;
}
}
for (int mask = 0; mask <= full; mask++)
for (int k = 0; k <= n; k++) dp[mask][k] = INF;
for (int r = 0; r < n; r++) dp[1 << r][0] = 0;
int ans = INF;
for (int k = 0; k < n; k++) {
for (int mask = 1; mask <= full; mask++) {
int val = dp[mask][k];
if (val >= INF) continue;
if (mask == full) { if (val < ans) ans = val; continue; }
int comp = full ^ mask;
ll mul = k + 1;
for (int T = comp; T; T = (T - 1) & comp) {
ll cost = 0, t = T;
while (t) { int v = __builtin_ctz(t); t &= t - 1; cost += dis[mask][v]; }
if (cost >= INF) continue;
ll nv = val + mul * cost;
if (nv < dp[mask | T][k + 1]) dp[mask | T][k + 1] = (int)nv;
}
}
}
char *op = ob;
if (ans >= INF) { op[0]='0'; op[1]='\n'; op += 2; }
else {
char t[16]; int kk = 0;
if (!ans) t[kk++] = '0';
while (ans) { t[kk++] = (char)('0' + ans % 10); ans /= 10; }
while (kk) *op++ = t[--kk];
*op++ = '\n';
}
fwrite(ob, 1, op - ob, stdout);
return 0;
}