// This code is AI-generated. (AI 生成的代码)
// NOIP2017 宝藏: branch-and-bound over growing the excavated set layer by
// layer. Neighbours are tried in increasing edge weight; the bound uses the
// sum of each unvisited node's cheapest incident edge times the current depth.
#include <stdio.h>
typedef long long ll;
enum { N = 13, INF = 1000000000 };
static int n, m, w[N][N], adj[N][N], deg[N], mn[N];
static int di[N], vis[N], cnt, best;
static ll tot, bound;
static char buf[1 << 16], ob[32];
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;
}
static void dfs(int st, int sti) {
for (int i = st; i <= cnt; i++) {
int si = vis[i];
ll lb = tot + bound * di[si];
if (lb >= best) return;
for (int j = sti; j < deg[si]; j++) {
int sj = adj[si][j];
if (!di[sj]) {
vis[++cnt] = sj;
bound -= mn[sj];
tot += (ll)di[si] * w[si][sj];
di[sj] = di[si] + 1;
dfs(i, j + 1);
di[sj] = 0;
tot -= (ll)di[si] * w[si][sj];
bound += mn[sj];
cnt--;
}
}
sti = 0;
}
if (cnt == n && tot < best) best = (int)tot;
}
int main() {
int len = (int)fread(buf, 1, sizeof(buf) - 1, stdin);
buf[len] = 0; gp = buf;
n = rd(); m = rd();
for (int i = 1; i <= n; i++) { deg[i] = 0; for (int j = 1; j <= n; j++) w[i][j] = INF; }
for (int i = 0; i < m; i++) {
int u = rd(), v = rd(), ww = rd();
if (ww < w[u][v]) w[u][v] = w[v][u] = ww;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j && w[i][j] < INF) adj[i][deg[i]++] = j;
for (int i = 1; i <= n; i++)
for (int a = 1; a < deg[i]; a++) {
int x = adj[i][a], b = a - 1;
while (b >= 0 && w[i][adj[i][b]] > w[i][x]) { adj[i][b + 1] = adj[i][b]; b--; }
adj[i][b + 1] = x;
}
for (int i = 1; i <= n; i++) mn[i] = deg[i] ? w[i][adj[i][0]] : INF;
bound = 0;
for (int i = 1; i <= n; i++) bound += mn[i];
best = INF;
for (int r = 1; r <= n; r++) {
if (!deg[r]) continue;
cnt = 1; vis[1] = r; tot = 0; di[r] = 1;
bound -= mn[r];
dfs(1, 0);
bound += mn[r]; di[r] = 0;
}
char *op = ob;
if (n == 1) { op[0] = '0'; op[1] = '\n'; op += 2; }
else {
char t[16]; int kk = 0;
while (best) { t[kk++] = (char)('0' + best % 10); best /= 10; }
while (kk) *op++ = t[--kk];
*op++ = '\n';
}
fwrite(ob, 1, op - ob, stdout);
return 0;
}