#include <bits/stdc++.h>
using namespace std;
template <int N, typename T>
struct MaxFlow {
  int l[N], tot, d[N], Q[N], s, t, u, v, src, sink, cur[N];
  struct Edge {
    int v, x;
    T cap;
  } E[111111];
  void add(int u, int v, T cap, T vcap = 0) {
    E[tot] = (Edge){v, l[u], cap};
    l[u] = tot++;
    E[tot] = (Edge){u, l[v], vcap};
    l[v] = tot++;
  }
  void init() {
    memset(l, -1, sizeof l);
    tot = 0;
  }
  bool bfs() {
    memset(d, -1, sizeof d);
    memcpy(cur, l, sizeof cur);
    d[src] = 0;
    s = t = 0;
    Q[t++] = src;
    while (s < t) {
      u = Q[s++];
      for (int i = l[u]; ~i; i = E[i].x) {
        v = E[i].v;
        if (d[v] == -1 && E[i].cap > 0) {
          Q[t++] = v;
          d[v] = d[u] + 1;
        }
      }
    }
    return d[sink] != -1;
  }
  T dfs(int u, T in) {
    if (u == sink) return in;
    T flow = 0, f;
    for (int i = l[u]; ~i; i = E[i].x) {
      v = E[i].v;
      if (d[v] == d[u] + 1 && E[i].cap) {
        if (f = dfs(v, min(in - flow, E[i].cap))) {
          flow += f;
          E[i].cap -= f;
          E[i ^ 1].cap += f;
          if (flow == in) break;
        }
      }
    }
    if (flow < in) d[u] = -1;
    return flow;
  }
  T dinic(int _src, int _sink) {
    src = _src;
    sink = _sink;
    T flow = 0;
    while (bfs()) flow += dfs(src, 123456789);
    return flow;
  }
};
const int N = 200 + 10;
MaxFlow<N, int> F;
int n, m;
int p[N];
bool vis[N];
void mark(int u) {
  vis[u] = true;
  for (int i = F.l[u]; ~i; i = F.E[i].x) {
    int v = F.E[i].v;
    if (!vis[v] && F.E[i].cap) {
      mark(v);
    }
  }
}
priority_queue<pair<int, int>> Q;
int tree[N][N];
int main() {
  int u, v, cap;
  F.init();
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d%d%d", &u, &v, &cap);
    u--;
    v--;
    F.add(u, v, cap, cap);
  }
  int answer = 0;
  for (int i = 1; i < n; i++) {
    int f = F.dinic(i, p[i]);
    memset(vis, false, sizeof vis);
    mark(i);
    for (int j = i + 1; j < n; j++) {
      if (vis[j] && p[j] == p[i]) {
        p[j] = i;
      }
    }
    tree[p[i]][i] = f;
    answer += f;
    for (int j = 0; j < m << 1; j += 2) {
      F.E[j].cap = F.E[j].cap + F.E[j ^ 1].cap >> 1;
      F.E[j ^ 1].cap = F.E[j].cap;
    }
  }
  printf("%d\n", answer);
  printf("1");
  for (int i = 1; i < n; i++) {
    if (tree[0][i]) {
      Q.push({tree[0][i], i});
    }
  }
  while (!Q.empty()) {
    u = Q.top().second;
    Q.pop();
    printf(" %d", u + 1);
    for (int i = 1; i < n; i++) {
      if (tree[u][i]) {
        Q.push({tree[u][i], i});
      }
    }
  }
  puts("");
  return 0;
}
