#include <bits/stdc++.h>
using namespace std;
template <class C>
void mini(C& _a4, C _b4) {
  _a4 = min(_a4, _b4);
}
template <class C>
void maxi(C& _a4, C _b4) {
  _a4 = max(_a4, _b4);
}
template <class TH>
void _dbg(const char* sdbg, TH h) {
  cerr << sdbg << '=' << h << endl;
}
template <class TH, class... TA>
void _dbg(const char* sdbg, TH h, TA... a) {
  while (*sdbg != ',') cerr << *sdbg++;
  cerr << '=' << h << ',';
  _dbg(sdbg + 1, a...);
}
struct Dinic {
  struct Edge {
    long long v, c, inv;
  };

 public:
  Dinic() { n = -1; }
  void AddEdge(long long a, long long b, long long cap, long long bi_dir) {
    if (n < max(a, b)) {
      n = max(n, max(a, b));
      ResizeVectors();
    }
    e_orig[a].push_back(Edge{b, cap, ((long long)(e_orig[b]).size())});
    e_orig[b].push_back(
        Edge{a, bi_dir * cap, ((long long)(e_orig[a]).size()) - 1});
  }
  long long MaxFlow(long long s, long long t) {
    e = e_orig;
    long long result = 0;
    while (Bfs(s, t)) {
      for (long long i = 0; i <= n; i++) {
        beg[i] = 0;
      }
      result += Dfs(s, t, kInf);
    }
    return result;
  }
  vector<bool> MinCut(long long s, long long t) {
    assert(!Bfs(s, t));
    vector<bool> res(n + 1);
    for (long long i = 0; i <= n; i++) {
      if (dis[i] <= n) {
        res[i] = true;
      }
    }
    return res;
  }

 private:
  long long n;
  vector<vector<Edge>> e_orig, e;
  vector<long long> dis, beg;
  vector<pair<long long, long long>> cut;
  bool Bfs(long long s, long long t) {
    for (long long i = 0; i <= n; i++) {
      dis[i] = n + 1;
    }
    dis[s] = 0;
    vector<long long> que;
    que.push_back(s);
    for (long long i = 0; i < ((long long)(que).size()); i++) {
      long long v = que[i];
      for (auto edge : e[v]) {
        long long nei = edge.v;
        if (edge.c && dis[nei] > dis[v] + 1) {
          dis[nei] = dis[v] + 1;
          que.push_back(nei);
          if (nei == t) {
            cut.clear();
            return true;
          }
        } else if (!edge.c) {
          cut.push_back(make_pair(v, nei));
        }
      }
    }
    return false;
  }
  long long Dfs(long long v, long long t, long long min_cap) {
    long long result = 0;
    if (v == t || min_cap == 0) {
      return min_cap;
    }
    for (long long& i = beg[v]; i < ((long long)(e[v]).size()); i++) {
      long long nei = e[v][i].v;
      long long c = e[v][i].c;
      if (dis[nei] == dis[v] + 1 && c > 0) {
        long long flow_here = Dfs(nei, t, min(min_cap, c));
        result += flow_here;
        min_cap -= flow_here;
        e[v][i].c -= flow_here;
        e[nei][e[v][i].inv].c += flow_here;
      }
      if (min_cap == 0) {
        break;
      }
    }
    return result;
  }
  void ResizeVectors() {
    e_orig.resize(n + 2);
    beg.resize(n + 2);
    dis.resize(n + 2);
  }
  static const long long kInf = 1e18;
};
struct GomoryHu {
  vector<vector<pair<long long, long long>>> graph;
  vector<vector<long long>> nodes;
  vector<bool> visited;
  vector<long long> groupId, contrId;
  vector<long long> edgeFrom, edgeTo, edgeLen;
  long long wnode;
  long long n;
  GomoryHu(long long N) : graph(N), visited(N), groupId(N), contrId(N), n(N) {}
  void addEdge(long long u, long long v, long long cap) {
    graph[u].emplace_back(v, cap);
    graph[v].emplace_back(u, cap);
  }
  void dfs(long long v, long long type) {
    visited[v] = true;
    contrId[v] = type;
    for (long long i = 0; i < ((long long)(edgeFrom).size()); i++) {
      if (edgeFrom[i] == v && !visited[edgeTo[i]]) {
        dfs(edgeTo[i], type);
      }
    }
  }
  vector<vector<pair<long long, long long>>> run() {
    vector<long long> allNodes(n);
    iota((allNodes).begin(), (allNodes).end(), 0);
    nodes = vector<vector<long long>>{allNodes};
    edgeFrom.clear();
    edgeTo.clear();
    edgeLen.clear();
    fill((groupId).begin(), (groupId).end(), 0);
    for (long long step = 0; step < n - 1; step++) {
      Dinic dinic;
      for (long long i = 0; i < ((long long)(nodes).size()); i++) {
        if (((long long)(nodes[i]).size()) > 1) {
          wnode = i;
          break;
        }
      }
      random_shuffle((nodes[wnode]).begin(), (nodes[wnode]).end());
      fill((visited).begin(), (visited).end(), false);
      visited[wnode] = true;
      for (long long i = 0; i < ((long long)(edgeFrom).size()); i++) {
        if (edgeFrom[i] == wnode) {
          dfs(edgeTo[i], edgeTo[i]);
        }
      }
      for (long long v = 0; v < n; v++) {
        long long a = groupId[v] == wnode ? v : contrId[groupId[v]] + n;
        for (auto& P : graph[v]) {
          long long b = groupId[P.first] == wnode
                            ? P.first
                            : contrId[groupId[P.first]] + n;
          dinic.AddEdge(a, b, P.second, 0);
        }
      }
      dinic.AddEdge(2 * n, 2 * n, 0, 0);
      long long a = nodes[wnode][0], b = nodes[wnode][1],
                f = dinic.MaxFlow(a, b);
      auto cut = dinic.MinCut(a, b);
      for (long long i = 0; i < ((long long)(edgeFrom).size()); i++) {
        if (edgeFrom[i] != wnode && edgeTo[i] == wnode &&
            !cut[edgeFrom[i] + n]) {
          edgeTo[i] = step + 1;
        }
        if (edgeTo[i] != wnode && edgeFrom[i] == wnode && !cut[edgeTo[i] + n]) {
          edgeFrom[i] = step + 1;
        }
      }
      edgeFrom.push_back(wnode);
      edgeTo.push_back(step + 1);
      edgeLen.push_back(f);
      edgeFrom.push_back(step + 1);
      edgeTo.push_back(wnode);
      edgeLen.push_back(f);
      vector<long long> A, B;
      for (long long v : nodes[wnode]) {
        (cut[v] ? A : B).push_back(v);
        if (!cut[v]) {
          groupId[v] = step + 1;
        }
      }
      nodes[wnode] = A;
      nodes.push_back(B);
    }
    vector<vector<pair<long long, long long>>> tree(n);
    for (long long i = 0; i < ((long long)(edgeFrom).size()); i++) {
      tree[nodes[edgeFrom[i]][0]].emplace_back(nodes[edgeTo[i]][0], edgeLen[i]);
    }
    return tree;
  }
};
int main() {
  long long N, M;
  cin >> N >> M;
  GomoryHu gomory(N);
  for (long long i = 0; i < M; i++) {
    long long u, v, c;
    cin >> u >> v >> c;
    gomory.addEdge(u - 1, v - 1, c);
  }
  auto V = gomory.run();
  vector<long long> connRoot(N);
  vector<list<long long>> vertList(N);
  iota((connRoot).begin(), (connRoot).end(), 0);
  for (long long i = 0; i < N; i++) {
    vertList[i].push_back(i);
  }
  vector<tuple<long long, long long, long long>> edges;
  for (long long i = 0; i < N; i++) {
    for (auto& P : V[i]) {
      if (i < P.first) {
        edges.emplace_back(-P.second, i, P.first);
      }
    }
  }
  sort((edges).begin(), (edges).end());
  long long sum = 0;
  for (auto E : edges) {
    long long from = get<1>(E), to = get<2>(E);
    sum -= get<0>(E);
    from = connRoot[from];
    to = connRoot[to];
    if (from > to) {
      swap(from, to);
    }
    (from, to);
    vertList[from].splice(vertList[from].end(), vertList[to]);
    for (long long i = 0; i < N; i++) {
      if (connRoot[i] == to) {
        connRoot[i] = from;
      }
    }
  }
  cout << sum << "\n";
  for (long long v : vertList[0]) {
    cout << v + 1 << " ";
  }
  cout << "\n";
}
