#include <bits/stdc++.h>
using namespace std;
template <class t>
inline void read(t &res) {
  char ch;
  while (ch = getchar(), !isdigit(ch))
    ;
  res = ch ^ 48;
  while (ch = getchar(), isdigit(ch)) res = res * 10 + (ch ^ 48);
}
template <class t>
inline void print(t x) {
  if (x > 9) print(x / 10);
  putchar(x % 10 + 48);
}
const int e = 505, o = 6005, inf = 0x3f3f3f3f;
int n, m, ans[e], cnt;
long long sum;
namespace dinic {
int adj[e], nxt[o], go[o], num, s, t, d[e], f[o], c[o], cur[e];
bool vis[e], inq[e];
inline void link(int x, int y, int v) {
  nxt[++num] = adj[x];
  adj[x] = num;
  go[num] = y;
  c[num] = v;
  nxt[++num] = adj[y];
  adj[y] = num;
  go[num] = x;
}
inline void clear() {
  int i;
  for (i = 2; i <= num; i++) f[i] = 0;
}
inline bool bfs() {
  int i;
  for (i = 1; i <= n; i++) {
    cur[i] = adj[i];
    vis[i] = 0;
  }
  queue<int> q;
  q.push(s);
  vis[s] = 1;
  d[s] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (i = adj[u]; i; i = nxt[i]) {
      int v = go[i];
      if (!vis[v] && c[i] > f[i]) {
        vis[v] = 1;
        q.push(v);
        d[v] = d[u] + 1;
      }
    }
  }
  return vis[t];
}
inline int dfs(int u, int a) {
  if (u == t || a == 0) return a;
  int flow = 0, f1;
  for (int &i = cur[u]; i; i = nxt[i]) {
    int v = go[i];
    if (d[v] == d[u] + 1 && (f1 = dfs(v, min(c[i] - f[i], a))) > 0) {
      f[i] += f1;
      f[i ^ 1] -= f1;
      flow += f1;
      a -= f1;
      if (a == 0) break;
    }
  }
  return flow;
}
inline void dfs(int u) {
  inq[u] = 1;
  for (int i = adj[u]; i; i = nxt[i]) {
    int v = go[i];
    if (c[i] > f[i] && !inq[v]) dfs(v);
  }
}
inline int solve(int u, int v) {
  s = u;
  t = v;
  clear();
  int i, w = 0;
  while (bfs()) w += dfs(s, inf);
  for (i = 1; i <= n; i++) inq[i] = 0;
  dfs(s);
  return w;
}
}  // namespace dinic
namespace cut {
int adj[e], nxt[o], go[o], num, len[o], pu, pv, pw, id;
bool vis[o];
inline void link(int x, int y, int z) {
  nxt[++num] = adj[x];
  adj[x] = num;
  go[num] = y;
  len[num] = z;
  nxt[++num] = adj[y];
  adj[y] = num;
  go[num] = x;
  len[num] = z;
}
inline void dfs(int u, int pa) {
  for (int i = adj[u]; i; i = nxt[i]) {
    int v = go[i];
    if (v == pa || vis[i]) continue;
    if (len[i] < pw) {
      pu = u;
      pv = v;
      pw = len[i];
      id = i;
    }
    dfs(v, u);
  }
}
inline void solve(int s) {
  pw = inf;
  dfs(s, 0);
  if (pw == inf) {
    ans[++cnt] = s;
    return;
  }
  vis[id] = vis[id ^ 1] = 1;
  int lv = pv;
  solve(pu);
  solve(lv);
}
}  // namespace cut
inline void build(vector<int> a) {
  if (a.size() < 2) return;
  int u = a[0], v = a[1], w = dinic::solve(u, v), i, l = a.size();
  cut::link(u, v, w);
  sum += w;
  vector<int> b(0), c(0);
  for (i = 0; i < l; i++)
    if (dinic::inq[a[i]])
      b.push_back(a[i]);
    else
      c.push_back(a[i]);
  build(b);
  build(c);
}
int main() {
  read(n);
  read(m);
  dinic::num = cut::num = 1;
  int i, u, v, w;
  while (m--) {
    read(u);
    read(v);
    read(w);
    dinic::link(u, v, w);
    dinic::link(v, u, w);
  }
  vector<int> a;
  for (i = 1; i <= n; i++) a.push_back(i);
  build(a);
  cut::solve(1);
  cout << sum << endl;
  for (i = 1; i <= n; i++) print(ans[i]), putchar(' ');
  return 0;
}
