#include <bits/stdc++.h>
using namespace std;
struct node {
  int x, s;
  bool operator<(node const &T) const { return s < T.s; }
};
int n, m, ed, x, y, z, S, T, V;
int v[205], g[205], p[205], l[205];
int qd[2005], qn[2005], qc[2005], qr[2005];
int flow[205][205], Tree[205][205];
priority_queue<node> q;
void bd(int x, int y, int c) {
  qd[++ed] = y, qn[ed] = l[x], l[x] = ed, qc[ed] = qr[ed] = c;
}
int ISAP(int x, int y) {
  int mn = V - 1, F = 0, R = y, t;
  if (x == T) return y;
  for (int i = l[x]; i; i = qn[i]) {
    if (qc[i] > 0) {
      if (v[x] == v[qd[i]] + 1) {
        t = ISAP(qd[i], min(qc[i], R));
        qc[i] -= t;
        qc[i ^ 1] += t;
        R -= t;
        F += t;
        if (v[S] >= V) return F;
        if (!R) break;
      }
      mn = min(mn, v[qd[i]]);
    }
  }
  if (!F) {
    g[v[x]]--;
    if (!g[v[x]]) v[S] = V;
    v[x] = mn + 1;
    g[v[x]]++;
  }
  return F;
}
int MaxFlow() {
  for (int i = (1); i <= (ed); i++) qc[i] = qr[i];
  memset(v, 0, sizeof(v));
  memset(g, 0, sizeof(g));
  int ret = 0;
  g[0] = V;
  while (v[S] < V) ret += ISAP(S, 1 << 30);
  return ret;
}
void FC(int x) {
  v[x] = 1;
  for (int i = (l[x]); i; i = qn[i])
    if (qc[i] && !v[qd[i]]) FC(qd[i]);
}
void solve() {
  int ret = 0;
  for (int i = (1); i <= (n); i++) p[i] = 1;
  for (int i = (2); i <= (n); i++) {
    for (int j = 2; j <= ed; j++) qc[j] = qr[j];
    S = i, T = p[i], V = n;
    int F = MaxFlow();
    memset(v, 0, sizeof(v));
    FC(i);
    for (int j = i + 1; j <= n; j++)
      if (v[j] && p[j] == p[i]) p[j] = i;
    Tree[p[i]][i] = F;
    ret += F;
  }
  printf("%d\n", ret);
  memset(v, 0, sizeof(v));
  printf("1 ");
  v[1] = 1;
  for (int i = (1); i <= (n); i++)
    if (Tree[1][i]) q.push((node){i, Tree[1][i]});
  while (!q.empty()) {
    node t = q.top();
    q.pop();
    printf("%d ", t.x);
    v[t.x] = 1;
    for (int i = (1); i <= (n); i++)
      if (Tree[t.x][i] && !v[i]) q.push((node){i, Tree[t.x][i]});
  }
}
int main() {
  scanf("%d%d", &n, &m);
  ed = 1;
  while (m--) scanf("%d%d%d", &x, &y, &z), bd(x, y, z), bd(y, x, z);
  solve();
  return 0;
}
