#include <bits/stdc++.h>
using namespace std;
void run();
int main() {
  ios::sync_with_stdio(0);
  run();
}
struct graph {
  map<int, int> edge[200];
};
int dist[200];
int dfs(graph &g, int s, int t, int cap = 1 << 29) {
  if (s == t or not cap) return cap;
  int res = 0;
  for (auto it = g.edge[s].begin(); cap and it != g.edge[s].end(); ++it) {
    if (dist[it->first] == dist[s] + 1) {
      int add = dfs(g, it->first, t, min(cap, it->second));
      g.edge[it->first][s] += add;
      it->second -= add;
      res += add;
      cap -= add;
    }
  }
  if (not res) dist[s] = -2;
  return res;
}
int maxflow(int s, int t, graph g) {
  for (int res = 0;;) {
    memset(dist, -1, sizeof dist);
    vector<int> bfs = {s};
    dist[s] = 0;
    for (int i = 0; i < bfs.size(); i++) {
      int x = bfs[i];
      for (auto y : g.edge[x]) {
        if (y.second and !~dist[y.first]) {
          dist[y.first] = dist[x] + 1;
          bfs.push_back(y.first);
        }
      }
    }
    if (!~dist[t]) {
      return res;
    }
    res += dfs(g, s, t);
  }
}
vector<pair<int, int>> child[200];
vector<int> answer[200];
int par[200];
int rnk[200];
int find(int a) { return par[a] == a ? a : par[a] = find(par[a]); }
int merge(int a, int b) {
  a = find(a);
  b = find(b);
  if (rnk[a] < rnk[b]) swap(a, b);
  if (a == b) return a;
  par[b] = a;
  rnk[a]++;
  return a;
}
void run() {
  int res = 0;
  graph g;
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    --a, --b;
    g.edge[a][b] = c;
    g.edge[b][a] = c;
  }
  int gom_hu[200] = {};
  int p[200] = {};
  for (int i = 1; i < n; i++) {
    gom_hu[i] = maxflow(i, p[i], g);
    res += gom_hu[i];
    for (int j = i + 1; j < n; j++) {
      if (p[j] == p[i] and ~dist[j]) {
        p[j] = i;
      }
    }
  }
  vector<pair<int, pair<int, int>>> important;
  for (int i = 1; i < n; i++) {
    important.push_back({gom_hu[i], {p[i], i}});
  }
  sort(important.begin(), important.end());
  cout << res << endl;
  for (int i = n; i--;) {
    answer[i] = {i};
    par[i] = i;
  }
  for (int i = important.size(); i--;) {
    int a = find(important[i].second.first);
    int b = find(important[i].second.second);
    vector<int> tmp;
    for (auto j : answer[a]) tmp.push_back(j);
    for (auto j : answer[b]) tmp.push_back(j);
    int c = merge(a, b);
    answer[c] = tmp;
  }
  for (int i = 0; i < n; i++)
    cout << answer[find(0)][i] + 1 << (i + 1 == n ? '\n' : ' ');
}
