#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0;
  bool f = 0;
  char c = getchar();
  for (; c < '0' || c > '9'; c = getchar()) f = c == '-' ? 1 : 0;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
  return f ? -x : x;
}
const int N = 205, M = 2005, oo = 0x3f3f3f3f;
int n, m, ll = 1, ec = 0, to[M], nxt[M], head[N], cur[N], fl[M], _fl[M], S, T,
          dis[N], qu[N], c[N], c1[N], c2[N], ans = 0, g[N][N];
struct na {
  int u, v, w;
} e[N];
inline void adde(int u, int v, int w) {
  to[++ll] = v;
  nxt[ll] = head[u];
  head[u] = ll;
  _fl[ll] = w;
  to[++ll] = u;
  nxt[ll] = head[v];
  head[v] = ll;
  _fl[ll] = w;
}
bool bfs() {
  memset(dis, 0, sizeof dis);
  int l = 0, r = 1;
  qu[0] = S;
  dis[S] = 1;
  while (l != r) {
    int u = qu[l++];
    for (int i = head[u]; i; i = nxt[i])
      if (!dis[to[i]] && fl[i]) dis[to[i]] = dis[u] + 1, qu[r++] = to[i];
  }
  return dis[T];
}
int dfs(int u, int f) {
  if (u == T) return f;
  int used = 0, tmp;
  for (int i = cur[u]; i; i = nxt[i])
    if (dis[to[i]] == dis[u] + 1 && fl[i] &&
        (tmp = dfs(to[i], min(f - used, fl[i])))) {
      fl[i] -= tmp;
      fl[i ^ 1] += tmp;
      used += tmp;
      if (fl[i]) cur[u] = i;
      if (used == f) return f;
    }
  if (!used) dis[u] = 0;
  return used;
}
void cal(int l, int r) {
  if (l >= r) return;
  int rec = 0, l1 = 0, l2 = 0, l3 = l;
  S = c[l];
  T = c[l + 1];
  memcpy(fl, _fl, sizeof _fl);
  while (bfs()) {
    memcpy(cur, head, sizeof head);
    rec += dfs(S, oo);
  }
  ans += rec;
  e[++ec] = (na){c[l], c[l + 1], rec};
  for (int i = l; i <= r; i++)
    if (dis[c[i]])
      c1[++l1] = c[i];
    else
      c2[++l2] = c[i];
  for (int i = 1; i <= l1; i++) c[l3++] = c1[i];
  for (int i = 1; i <= l2; i++) c[l3++] = c2[i];
  cal(l, l + l1 - 1);
  cal(l + l1, r);
}
int _p;
void dfs_find(int u, int f) {
  for (int i = head[u]; i; i = nxt[i])
    if (_fl[i] && (to[i] != f)) {
      (_fl[i] < _fl[_p]) ? (_p = i) : 0;
      dfs_find(to[i], u);
    }
}
void dfscal(int u) {
  _p = 0;
  dfs_find(u, 0);
  if (!_p) {
    printf("%d ", u);
    return;
  }
  _fl[_p] = _fl[_p ^ 1] = 0;
  int u1 = to[_p], u2 = to[_p ^ 1];
  dfscal(u1), dfscal(u2);
}
int main() {
  n = read();
  m = read();
  for (int i = 1, u, v, w; i <= m; i++)
    u = read(), v = read(), w = read(), adde(u, v, w);
  for (int i = 1; i <= n; i++) c[i] = i;
  cal(1, n);
  printf("%d\n", ans);
  ll = 1;
  memset(head, 0, sizeof head);
  _fl[0] = oo;
  for (int i = 1; i < n; i++) adde(e[i].u, e[i].v, e[i].w);
  dfscal(1);
  return 0;
}
