#include <bits/stdc++.h>
using namespace std;
const long long oo = 0x3f3f3f3f3f3f3f3fLL;
struct Edge {
  int u, v;
  long long cap[2], flow;
};
vector<int> d, act;
bool bfs(int s, int t, vector<vector<int>>& adj, vector<Edge>& E,
         long long lim = 1) {
  queue<int> Q;
  d = vector<int>(adj.size(), -1);
  d[t] = 0;
  Q.push(t);
  for (Q.push(t); Q.size() and d[s] == -1; Q.pop()) {
    int u = Q.front();
    for (int i = (0); i < int(adj[u].size()); i++) {
      int e = adj[u][i], v = (E[e].u ^ E[e].v ^ u);
      if (((E[e].u == v) ? E[e].cap[0] - E[e].flow : E[e].cap[1] + E[e].flow) >=
              lim and
          d[v] == -1) {
        d[v] = d[u] + 1;
        Q.push(v);
      }
    }
  }
  return d[s] >= 0;
}
long long dfs(int u, int t, long long bot, vector<vector<int>>& adj,
              vector<Edge>& E) {
  if (bot == 0) return 0;
  if (u == t) return bot;
  for (; act[u] < int(adj[u].size()); ++act[u]) {
    int e = adj[u][act[u]];
    if (d[u] == d[(E[e].u ^ E[e].v ^ u)] + 1) {
      long long inc = dfs((E[e].u ^ E[e].v ^ u), t,
                          min(bot, ((E[e].u == u) ? E[e].cap[0] - E[e].flow
                                                  : E[e].cap[1] + E[e].flow)),
                          adj, E);
      if (inc) {
        E[e].flow += ((E[e].u == u) ? (inc) : (-(inc)));
        return inc;
      }
    }
  }
  return 0;
}
long long maxflow(int s, int t, vector<vector<int>>& adj, vector<Edge>& E,
                  int F = 0) {
  for (auto& e : E) e.flow = 0;
  long long flow = 0, bot;
  for (int lim = (1 << F); lim >= 1; lim >>= 1) {
    while (bfs(s, t, adj, E, lim)) {
      act = vector<int>(adj.size(), 0);
      while ((bot = dfs(s, t, oo, adj, E))) flow += bot;
    }
  }
  return flow;
}
inline void addEdge(int x, int y, vector<vector<int>>& adj, vector<Edge>& E,
                    long long c, long long rc = 0) {
  Edge e;
  e.u = x;
  e.v = y;
  e.flow = 0;
  e.cap[0] = c;
  e.cap[1] = rc;
  adj[x].push_back(int((E).size()));
  adj[y].push_back(int((E).size()));
  E.push_back(e);
}
long long anss = 0;
void gomory_hu(vector<vector<int>>& adj, vector<Edge>& E, vector<int>& parent,
               vector<vector<long long>>& ans) {
  int n = int((adj).size());
  parent.assign(n, 0);
  ans.assign(n, vector<long long>(n, oo));
  for (int i = (1); i < int(n); i++) {
    long long f = maxflow(i, parent[i], adj, E);
    anss += f;
    bfs(i, parent[i], adj, E);
    for (int j = (i + 1); j < int(n); j++)
      if (d[j] == -1 and parent[j] == parent[i]) parent[j] = i;
    ans[i][parent[i]] = ans[parent[i]][i] = f;
    for (int j = (0); j < int(i); j++)
      ans[i][j] = ans[j][i] = min(f, ans[parent[i]][j]);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> adj(n);
  vector<Edge> E;
  for (int i = (0); i < int(m); i++) {
    int a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    addEdge(a, b, adj, E, c, c);
  }
  vector<int> par;
  vector<vector<long long>> d;
  gomory_hu(adj, E, par, d);
  cout << anss << endl;
  int best = 0;
  vector<int> res(n);
  for (int i = 0; i < n; ++i) {
    res[i] = i;
  }
  for (int i = 0; i < 1; ++i) {
    vector<int> order;
    order.push_back(i);
    vector<int> used(n, 0);
    used[i] = true;
    int score = 0;
    while (int((order).size()) != n) {
      int best = -1, index = -1;
      for (int j = 0; j < n; ++j) {
        if (!used[j] && d[order.back()][j] > best) {
          best = d[order.back()][j];
          index = j;
        }
      }
      score += best;
      order.push_back(index);
      used[index] = true;
    }
    if (score > best) {
      best = score;
      res = order;
    }
  }
  for (int i = 0; i < res.size(); ++i) {
    printf("%d ", res[i] + 1);
  }
  printf("\n");
}
