#include <bits/stdc++.h>
using namespace std;
int n, m, s, t;
const int maxn = 2e2 + 5;
const int maxm = 4e3 + 5;
struct edge {
  int to, nex, w;
} e[maxm];
int head[maxn], cur[maxn], cnt = 1;
int dis[maxn];
void add(int a, int b, int c) {
  e[++cnt] = (edge){b, head[a], c};
  head[a] = cnt;
}
void addedge(int a, int b, int c) { add(a, b, c), add(b, a, 0); }
bool bfs() {
  queue<int> Q;
  for (int i = 1; i <= n; ++i) dis[i] = 0, cur[i] = head[i];
  dis[s] = 1;
  Q.push(s);
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (int i = head[u]; i; i = e[i].nex) {
      int v = e[i].to;
      if (e[i].w && (!dis[v])) {
        dis[v] = dis[u] + 1;
        Q.push(v);
      }
    }
  }
  return dis[t];
}
int dfs(int u, int in) {
  if (u == t) return in;
  int out = 0;
  for (int i = cur[u]; i; i = e[i].nex) {
    int v = e[i].to;
    cur[u] = i;
    if (e[i].w && dis[v] == dis[u] + 1) {
      int tmp = dfs(v, min(in, e[i].w));
      e[i].w -= tmp, e[i ^ 1].w += tmp;
      in -= tmp, out += tmp;
      if (!in) break;
    }
  }
  if (!out) dis[u] = 0;
  return out;
}
void init() {
  for (int i = 2; i <= cnt; i += 2) {
    e[i].w = e[i].w + e[i ^ 1].w;
    e[i ^ 1].w = 0;
  }
}
int dinic(int a, int b) {
  s = a, t = b;
  int tmp = 0;
  init();
  while (bfs()) tmp += dfs(s, 1e9);
  return tmp;
}
int id[maxn];
vector<pair<int, int> > tr[maxn];
int ans[maxn][maxn];
int a1 = 0;
vector<int> p;
void build(int l, int r) {
  if (l == r) return;
  int x = id[l], y = id[r];
  int w = dinic(x, y);
  tr[x].emplace_back(y, w), tr[y].emplace_back(x, w);
  a1 += w;
  vector<int> t1, t2;
  for (int i = l; i <= r; ++i) {
    if (dis[id[i]])
      t1.emplace_back(id[i]);
    else
      t2.emplace_back(id[i]);
  }
  for (int i = 1; i <= n; ++i)
    if (dis[i])
      for (int j = 1; j <= n; ++j)
        if (!dis[j]) ans[i][j] = ans[j][i] = min(ans[i][j], w);
  for (int i = 0; i < t1.size(); ++i) id[i + l] = t1[i];
  for (int i = 0; i < t2.size(); ++i) id[i + t1.size() + l] = t2[i];
  build(l, l + t1.size() - 1);
  build(l + t1.size(), r);
  return;
}
int vis[maxn];
void solve(int x, int num) {
  p.clear();
  memset(vis, 0, sizeof vis);
  p.emplace_back(x);
  vis[x] = 1;
  int tmp = 0;
  for (int i = 1; i <= n - 1; ++i) {
    int mx = 0, id;
    for (int j = 1; j <= n; ++j) {
      if (vis[j]) continue;
      if (ans[x][j] > mx) mx = ans[x][j], id = j;
    }
    tmp += mx, x = id, vis[id] = 1;
    p.emplace_back(x);
  }
  for (auto y : p) cout << y << ' ';
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    addedge(a, b, c), addedge(b, a, c);
  }
  for (int i = 1; i <= n; ++i) id[i] = i;
  memset(ans, 0x3f, sizeof ans);
  build(1, n);
  cout << a1 << '\n';
  solve(1, a1);
  return 0;
}
