#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct Edge {
  long long from, to;
  T cost;
  Edge(long long to, T cost) : from(-1), to(to), cost(cost) {}
  Edge(long long from, long long to, T cost) : from(from), to(to), cost(cost) {}
  bool operator<(const Edge &e) const { return cost < e.cost; }
  bool operator>(const Edge &e) const { return cost > e.cost; }
};
template <typename T>
using Edges = vector<Edge<T> >;
template <typename T>
struct Dinic {
  T INF = 1 << 28;
  struct FlowEdge {
    long long to, rev;
    T cap;
    FlowEdge() {}
    FlowEdge(long long to, T cap, long long rev) : to(to), cap(cap), rev(rev) {}
  };
  long long n;
  vector<vector<FlowEdge> > G;
  vector<long long> level;
  vector<long long> iter;
  Dinic() {}
  Dinic(long long sz) : n(sz), G(n), level(n), iter(n) {}
  void add_edge(long long from, long long to, T cap) {
    G[from].push_back(FlowEdge(to, cap, G[to].size()));
    G[to].push_back(FlowEdge(from, cap, G[from].size() - 1));
  }
  void bfs(long long s) {
    fill(level.begin(), level.end(), -1);
    queue<long long> Q;
    level[s] = 0;
    Q.push(s);
    while (!Q.empty()) {
      long long v = Q.front();
      Q.pop();
      for (long long i = 0; i < (long long)G[v].size(); i++) {
        FlowEdge &e = G[v][i];
        if (e.cap > 0 && level[e.to] < 0) {
          level[e.to] = level[v] + 1;
          Q.push(e.to);
        }
      }
    }
  }
  T dfs(long long v, long long t, T f) {
    if (v == t) return f;
    for (long long &i = iter[v]; i < (long long)G[v].size(); i++) {
      FlowEdge &e = G[v][i];
      if (e.cap > 0 && level[v] < level[e.to]) {
        T d = dfs(e.to, t, min(f, e.cap));
        if (d > 0) {
          e.cap -= d;
          G[e.to][e.rev].cap += d;
          return d;
        }
      }
    }
    return 0;
  }
  T max_flow(long long s, long long t, long long lim) {
    T flow = 0;
    while (1) {
      bfs(s);
      if (level[t] < 0 || lim == 0) return flow;
      fill(iter.begin(), iter.end(), 0);
      T f;
      while ((f = dfs(s, t, lim)) > 0) {
        flow += f;
        lim -= f;
      }
    }
  }
  T max_flow(long long s, long long t) { return max_flow(s, t, INF); }
  vector<bool> get_cut() {
    vector<bool> res(n);
    for (long long i = 0; i < n; i++) {
      res[i] = (level[i] == -1);
    }
    return res;
  }
};
template <typename T>
struct GomoryHu {
  long long n;
  Dinic<T> dinic;
  Edges<T> GH;
  GomoryHu() {}
  GomoryHu(long long sz) : n(sz), dinic(n) {}
  void add_edge(long long from, long long to, T cap) {
    dinic.add_edge(from, to, cap);
  }
  Edges<T> build() {
    Edges<T> ret;
    vector<long long> pr(n, 0);
    Dinic<T> tmp = dinic;
    for (long long i = 1; i < n; i++) {
      dinic = tmp;
      T flow = dinic.max_flow(i, pr[i]);
      vector<bool> cut = dinic.get_cut();
      for (long long j = i + 1; j < n; j++) {
        if (cut[j] == cut[i] && pr[j] == pr[i]) {
          pr[j] = i;
        }
      }
      ret.emplace_back(Edge<T>(i, pr[i], flow));
    }
    return GH = ret;
  }
};
struct UnionFind {
  long long n;
  vector<long long> r, p;
  UnionFind() {}
  UnionFind(long long sz) : n(sz), r(sz, 1), p(sz, 0) {
    iota(p.begin(), p.end(), 0);
  }
  long long find(long long x) { return (x == p[x] ? x : p[x] = find(p[x])); }
  bool same(long long x, long long y) { return find(x) == find(y); }
  void unite(long long x, long long y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    r[x] += r[y];
    p[y] = x;
  }
};
signed main() {
  long long n, m;
  cin >> n >> m;
  GomoryHu<long long> gh(n);
  for (long long i = 0; i < m; i++) {
    long long a, b, c;
    cin >> a >> b >> c;
    a--;
    b--;
    gh.add_edge(a, b, c);
  }
  Edges<long long> tree = gh.build();
  long long sum = 0;
  for (Edge<long long> e : tree) {
    sum += e.cost;
  }
  cout << sum << endl;
  vector<pair<long long, long long> > edges;
  for (long long i = 0; i < n - 1; i++) {
    edges.emplace_back(tree[i].cost, i);
  }
  sort(edges.begin(), edges.end(), greater<pair<long long, long long> >());
  UnionFind uf(n);
  vector<vector<long long> > seq(n);
  for (long long i = 0; i < n; i++) seq[i].emplace_back(i);
  for (long long i = 0; i < n - 1; i++) {
    Edge<long long> e = tree[edges[i].second];
    long long x = uf.find(e.from), y = uf.find(e.to);
    uf.unite(x, y);
    seq[x].insert(seq[x].end(), seq[y].begin(), seq[y].end());
  }
  vector<long long> ans = seq[uf.find(0)];
  for (long long i = 0; i < n; i++) {
    if (i) cout << " ";
    cout << ans[i] + 1;
  }
  cout << endl;
  return 0;
}
