#include <bits/stdc++.h>
using namespace std;
long long INF = (1ULL << 50);
struct edge {
  int src, dst;
  long long capacity;
  int rev;
  long long residue;
};
struct graph {
  int n;
  vector<vector<edge>> adj;
  graph(int n = 0) : n(n), adj(n) {}
  void add_edge(int src, int dst, long long capacity) {
    adj[src].push_back({src, dst, capacity, (int)adj[dst].size()});
    adj[dst].push_back({dst, src, capacity, (int)adj[src].size() - 1});
  }
  vector<int> level, iter;
  long long augment(int u, int t, long long cur) {
    if (u == t) return cur;
    for (int &i = iter[u]; i < adj[u].size(); ++i) {
      edge &e = adj[u][i];
      if (e.residue > 0 && level[u] < level[e.dst]) {
        long long f = augment(e.dst, t, min(cur, e.residue));
        if (f > 0) {
          e.residue -= f;
          adj[e.dst][e.rev].residue += f;
          return f;
        }
      }
    }
    return 0;
  }
  int bfs(int s, int t) {
    level.assign(n, -1);
    level[s] = 0;
    queue<int> Q;
    Q.push(s);
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      if (u == t) break;
      for (auto &e : adj[u]) {
        if (e.residue > 0 && level[e.dst] < 0) {
          Q.push(e.dst);
          level[e.dst] = level[u] + 1;
        }
      }
    }
    return level[t];
  }
  long long max_flow(int s, int t) {
    for (int u = 0; u < n; ++u)
      for (auto &e : adj[u]) e.residue = e.capacity;
    long long flow = 0;
    int itera = 0;
    while (bfs(s, t) >= 0) {
      iter.assign(n, 0);
      for (long long f; (f = augment(s, t, INF)) > 0;) flow += f;
    }
    return flow;
  }
  vector<edge> tree;
  vector<int> parent;
  void gomory_hu() {
    tree.clear();
    parent.clear();
    parent.resize(n);
    for (int i = 0; i < n; ++i) parent[i] = 0;
    for (int u = 1; u < n; ++u) {
      tree.push_back({u, parent[u], max_flow(u, parent[u])});
      for (int v = u + 1; v < n; ++v)
        if (level[v] >= 0 && parent[v] == parent[u]) parent[v] = u;
    }
  }
};
struct ed {
  int u;
  long long cap;
};
vector<ed> par;
struct ted {
  int u;
  long long cap;
  int rev;
  bool tak;
};
vector<vector<ted>> adj;
int n;
vector<bool> vis;
long long dfs(int x) {
  vis[x] = 1;
  long long ans = INF;
  for (int i = 0; i < (int)adj[x].size(); ++i) {
    ted nxt = adj[x][i];
    if (!nxt.tak && !vis[nxt.u]) {
      ans = min(ans, nxt.cap);
      ans = min(ans, dfs(nxt.u));
    }
  }
  return ans;
}
bool f = 0;
pair<int, int> dfs2(int x, long long val) {
  vis[x] = 1;
  pair<int, int> ans = make_pair(-1, -1);
  for (int i = 0; i < (int)adj[x].size(); ++i) {
    ted nxt = adj[x][i];
    if (!nxt.tak && !vis[nxt.u]) {
      if (!f && nxt.cap == val) {
        f = 1;
        ans = make_pair(x, nxt.u);
        adj[x][i].tak = 1;
        adj[nxt.u][adj[x][i].rev].tak = 1;
      }
      pair<int, int> maybe = dfs2(nxt.u, val);
      if (maybe.first != -1) ans = maybe;
    }
  }
  return ans;
}
vector<int> perm(int x) {
  vis.resize(n);
  for (int i = 0; i < n; ++i) vis[i] = 0;
  long long val = dfs(x);
  if (val >= INF) return {x};
  for (int i = 0; i < n; ++i) vis[i] = 0;
  f = 0;
  pair<int, int> tr = dfs2(x, val);
  vector<int> a1 = perm(tr.first), a2 = perm(tr.second);
  vector<int> ans = a1;
  for (int i = 0; i < (int)a2.size(); ++i) ans.push_back(a2[i]);
  return ans;
}
int main() {
  int m;
  cin >> n >> m;
  graph g(n);
  for (int i = 0; i < m; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    g.add_edge(a - 1, b - 1, c);
  }
  g.gomory_hu();
  vector<edge> tree = g.tree;
  vector<int> parent = g.parent;
  par.resize(n);
  par[0] = {-1, 0};
  adj.resize(n);
  long long ans = 0;
  for (int i = 0; i < (int)tree.size(); ++i) {
    if (parent[tree[i].src] == tree[i].dst) {
      par[tree[i].src] = {tree[i].dst, tree[i].capacity};
    } else {
      par[tree[i].dst] = {tree[i].src, tree[i].capacity};
    }
    cerr << tree[i].src << " " << tree[i].dst << " " << tree[i].capacity
         << endl;
    ans += tree[i].capacity;
    int a = adj[tree[i].src].size();
    int b = adj[tree[i].dst].size();
    adj[tree[i].src].push_back({tree[i].dst, tree[i].capacity, b, 0});
    adj[tree[i].dst].push_back({tree[i].src, tree[i].capacity, a, 0});
  }
  vector<int> p = perm(0);
  cout << ans << endl;
  for (int i = 0; i < n; ++i) cout << p[i] + 1 << " ";
  cout << endl;
  return 0;
}
