#include <bits/stdc++.h>
using namespace std;
template <typename T>
class graph {
 public:
  struct edge {
    int from;
    int to;
    T cost;
  };
  vector<edge> edges;
  vector<vector<int> > g;
  int n;
  graph(int n) : n(n) { g.resize(n); }
  virtual void add(int from, int to, T cost) = 0;
};
template <typename T>
class undigraph : public graph<T> {
 public:
  using graph<T>::edges;
  using graph<T>::g;
  using graph<T>::n;
  undigraph(int n) : graph<T>(n) {}
  void add(int from, int to, T cost = 1) {
    assert(0 <= from && from < n && 0 <= to && to < n);
    g[from].push_back(edges.size());
    g[to].push_back(edges.size());
    edges.push_back({from, to, cost});
  }
};
template <typename T>
class forest : public graph<T> {
 public:
  using graph<T>::edges;
  using graph<T>::g;
  using graph<T>::n;
  forest(int n) : graph<T>(n) {}
  void add(int from, int to, T cost = 1) {
    assert(0 <= from && from < n && 0 <= to && to < n);
    g[from].push_back(edges.size());
    g[to].push_back(edges.size());
    edges.push_back({from, to, cost});
  }
};
template <typename T>
class flow_graph {
 public:
  static constexpr T eps = (T)1e-9;
  struct edge {
    int to;
    T c;
    T f;
    int rev;
  };
  vector<vector<edge> > g;
  vector<int> ptr;
  vector<int> d;
  vector<int> q;
  int n;
  int st, fin;
  T flow;
  flow_graph(int n, int st, int fin) : n(n), st(st), fin(fin) {
    assert(0 <= st && st < n && 0 <= fin && fin < n && st != fin);
    g.resize(n);
    ptr.resize(n);
    d.resize(n);
    q.resize(n);
    flow = 0;
  }
  void clear_flow() {
    for (int i = 0; i < n; i++) {
      for (edge &e : g[i]) {
        e.f = 0;
      }
    }
    flow = 0;
  }
  void add(int from, int to, T forward_cap, T backward_cap) {
    assert(0 <= from && from < n && 0 <= to && to < n);
    int from_size = g[from].size();
    int to_size = g[to].size();
    g[from].push_back({to, forward_cap, 0, to_size});
    g[to].push_back({from, backward_cap, 0, from_size});
  }
  bool expath() {
    fill(d.begin(), d.end(), -1);
    q[0] = fin;
    d[fin] = 0;
    int beg = 0, end = 1;
    while (beg < end) {
      int i = q[beg++];
      for (const edge &e : g[i]) {
        const edge &back = g[e.to][e.rev];
        if (back.c - back.f > eps && d[e.to] == -1) {
          d[e.to] = d[i] + 1;
          if (e.to == st) {
            return true;
          }
          q[end++] = e.to;
        }
      }
    }
    return false;
  }
  T dfs(int v, T w) {
    if (v == fin) {
      return w;
    }
    int &j = ptr[v];
    while (j >= 0) {
      const edge &e = g[v][j];
      if (e.c - e.f > eps && d[e.to] == d[v] - 1) {
        T t = dfs(e.to, min(e.c - e.f, w));
        if (t > eps) {
          g[v][j].f += t;
          g[e.to][e.rev].f -= t;
          return t;
        }
      }
      j--;
    }
    return 0;
  }
  T max_flow() {
    while (expath()) {
      for (int i = 0; i < n; i++) {
        ptr[i] = (int)g[i].size() - 1;
      }
      T big_add = 0;
      while (true) {
        T add = dfs(st, numeric_limits<T>::max());
        if (add <= eps) {
          break;
        }
        big_add += add;
      }
      if (big_add <= eps) {
        break;
      }
      flow += big_add;
    }
    return flow;
  }
  vector<bool> min_cut() {
    max_flow();
    vector<bool> ret(n);
    for (int i = 0; i < n; i++) {
      ret[i] = (d[i] != -1);
    }
    return ret;
  }
};
template <typename T>
forest<T> gomory_hu(const undigraph<T> &g) {
  int n = g.n;
  flow_graph<T> fg(n, 0, 1);
  for (auto &e : g.edges) {
    fg.add(e.from, e.to, e.cost, e.cost);
  }
  forest<T> ret(n);
  vector<int> pr(n, 0);
  for (int i = 1; i < n; i++) {
    fg.clear_flow();
    fg.st = i;
    fg.fin = pr[i];
    T flow = fg.max_flow();
    vector<bool> cut = fg.min_cut();
    for (int j = i + 1; j < n; j++) {
      if (cut[j] == cut[i] && pr[j] == pr[i]) {
        pr[j] = i;
      }
    }
    ret.add(i, pr[i], flow);
  }
  return ret;
}
class dsu {
 public:
  vector<int> p;
  int n;
  vector<vector<int> > seq;
  dsu(int n) : n(n) {
    p.resize(n);
    iota(p.begin(), p.end(), 0);
    seq.resize(n);
    for (int i = 0; i < n; i++) {
      seq[i].push_back(i);
    }
  }
  inline int get(int x) { return (x == p[x] ? x : (p[x] = get(p[x]))); }
  inline bool unite(int x, int y) {
    x = get(x);
    y = get(y);
    if (x != y) {
      p[x] = y;
      seq[y].insert(seq[y].end(), seq[x].begin(), seq[x].end());
      return true;
    }
    return false;
  }
};
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  undigraph<int> g(n);
  for (int i = 0; i < m; i++) {
    int x, y, z;
    scanf("%d %d %d", &x, &y, &z);
    x--;
    y--;
    g.add(x, y, z);
  }
  forest<int> t = gomory_hu(g);
  int sum = 0;
  for (auto &e : t.edges) {
    sum += e.cost;
  }
  vector<pair<int, int> > edges;
  for (int i = 0; i < n - 1; i++) {
    edges.emplace_back(t.edges[i].cost, i);
  }
  sort(edges.rbegin(), edges.rend());
  dsu d(n);
  for (int id = 0; id < n - 1; id++) {
    int i = edges[id].second;
    auto &e = t.edges[i];
    d.unite(e.from, e.to);
  }
  vector<int> res = d.seq[d.get(0)];
  printf("%d\n", sum);
  for (int i = 0; i < n; i++) {
    if (i > 0) {
      putchar(' ');
    }
    printf("%d", res[i] + 1);
  }
  printf("\n");
  return 0;
}
