#include <bits/stdc++.h>
using namespace std;
const int N = 203, M = 2005, INF = 0x3f3f3f3f;
int n, m, ans, zhan[N], b[N][N];
int src, des, cur[N], lev[N];
int amo = 1, info[N], nxt[M], go[M], cap[M];
inline void SetE(const int &x, const int &y, const int &z) {
  nxt[++amo] = info[x];
  go[info[x] = amo] = y;
  cap[amo] = z;
  nxt[++amo] = info[y];
  go[info[y] = amo] = x;
  cap[amo] = z;
}
inline bool modLevel() {
  static int ql, que[N];
  memset(lev, 0, sizeof(lev));
  que[ql = 1] = src;
  lev[src] = 1;
  for (int i = (1); i <= (ql); ++i) {
    int x = que[i];
    cur[x] = info[x];
    for (int k = info[x], y; y = go[k], k; k = nxt[k])
      if (cap[k] && !lev[y]) lev[y] = lev[x] + 1, que[++ql] = y;
  }
  return lev[des];
}
inline int Dinic(const int &x, const int &flow) {
  if (x == des) return flow;
  int y, delta, res = flow;
  for (int &k = cur[x]; y = go[k], k; k = nxt[k])
    if (cap[k] && lev[x] < lev[y]) {
      delta = Dinic(y, min(cap[k], res));
      if (delta) {
        cap[k] -= delta;
        cap[k ^ 1] += delta;
        if (!(res -= delta)) break;
      }
    }
  if (res) lev[x] = 0;
  return flow - res;
}
inline int max_flow() {
  int res = 0;
  while (modLevel()) res += Dinic(src, INF);
  return res;
}
inline void build_tree() {
  if (zhan[0] == 1) return;
  int zhan1[N], zhan2[N];
  for (int k = 2; k <= amo; k += 2)
    cap[k] = cap[k ^ 1] = cap[k] + cap[k ^ 1] >> 1;
  src = zhan[1];
  des = zhan[2];
  int res = max_flow();
  b[src][des] = b[des][src] = res;
  ans += res;
  zhan1[0] = zhan2[0] = 0;
  for (int i = (1); i <= (zhan[0]); ++i) {
    if (lev[zhan[i]])
      zhan1[++zhan1[0]] = zhan[i];
    else
      zhan2[++zhan2[0]] = zhan[i];
  }
  for (int i = (0); i <= (zhan1[0]); ++i) zhan[i] = zhan1[i];
  build_tree();
  for (int i = (0); i <= (zhan2[0]); ++i) zhan[i] = zhan2[i];
  build_tree();
}
inline void Bfs(const int &st) {
  static int ql, que[N];
  memset(lev, 0, sizeof(lev));
  que[ql = 1] = st;
  lev[st] = 1;
  for (int i = (1); i <= (ql); ++i) {
    int x = que[i];
    for (int y = (1); y <= (n); ++y)
      if (b[x][y] && !lev[y]) lev[y] = lev[x] + 1, que[++ql] = y;
  }
}
inline void print_prog() {
  if (zhan[0] == 1) {
    printf("%d ", zhan[1]);
    return;
  }
  int x = 0, y = 0;
  for (int i = (1); i <= (zhan[0]); ++i)
    for (int j = (1); j <= (zhan[0]); ++j)
      if (i != j)
        if (b[zhan[i]][zhan[j]] && (!x || b[zhan[i]][zhan[j]] < b[x][y]))
          x = zhan[i], y = zhan[j];
  b[x][y] = b[y][x] = 0;
  int zhan1[N], zhan2[N];
  Bfs(x);
  zhan1[0] = zhan2[0] = 0;
  for (int i = (1); i <= (zhan[0]); ++i) {
    if (lev[zhan[i]])
      zhan1[++zhan1[0]] = zhan[i];
    else
      zhan2[++zhan2[0]] = zhan[i];
  }
  for (int i = (0); i <= (zhan1[0]); ++i) zhan[i] = zhan1[i];
  print_prog();
  for (int i = (0); i <= (zhan2[0]); ++i) zhan[i] = zhan2[i];
  print_prog();
}
char ch;
inline int read() {
  while (ch = getchar(), ch < '0' || ch > '9')
    ;
  int res = ch - 48;
  while (ch = getchar(), ch >= '0' && ch <= '9') res = res * 10 + ch - 48;
  return res;
}
int main() {
  n = read();
  m = read();
  for (int i = (1); i <= (m); ++i) {
    int x = read(), y = read(), z = read();
    SetE(x, y, z);
  }
  for (int i = (1); i <= (n); ++i) zhan[++zhan[0]] = i;
  build_tree();
  printf("%d\n", ans);
  zhan[0] = 0;
  for (int i = (1); i <= (n); ++i) zhan[++zhan[0]] = i;
  print_prog();
  return 0;
}
