#include <bits/stdc++.h>
using namespace std;
int n, m, a[15][15], *b, t[(1 << 15) + 1], val[15][(1 << 15) + 1],
    f[(1 << 15) + 1][15], q[(1 << 15) + 1], l, r, i, j, k, x, y;
bool vis[(1 << 15) + 1];
inline void upd(int& a, int b) { a = a < b ? a : b; }
int main() {
  scanf("%d%d", &n, &m);
  while (m--)
    scanf("%d%d%d", &x, &y, &k), a[x - 1][y - 1] = a[y - 1][x - 1] = k;
  for (i = 0; i < n; i++) t[1 << i] = i;
  for (i = 0; i < n; i++)
    for (j = 1; j < (1 << n); j++)
      for (k = 0; k < n; k++)
        if ((j & (1 << k))) val[i][j] += a[i][k];
  q[l = r = 0] = 1;
  while (l <= r) {
    x = q[l++], vis[x] = 1;
    for (i = 0; i < n; i++)
      if (x & (1 << i))
        for (j = 0; j < n; j++)
          if (!(x & (1 << j)) && a[i][j] && !vis[x | (1 << j)]) {
            q[++r] = x | (1 << j), vis[x | (1 << j)] = 1;
            break;
          }
  }
  for (i = 3; i < (1 << n); i++)
    if (vis[i])
      for (j = 1; j < n; j++)
        if (i & (1 << j)) {
          f[i][j] = 0x3f3f3f3f;
          for (x = 0; x < n; x++)
            if ((i & (1 << x)) && a[j][x])
              upd(f[i][j], f[i ^ (1 << j)][x] + val[j][i ^ (1 << x)]);
          for (k = n - 1; ~k; k--) putchar('0' + ((i >> k) & 1));
          printf(" %d %d\n", j, f[i][j]);
        }
  printf("%d", f[(1 << n) - 1][n - 1]);
  return 0;
}
