#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && (c != '-')) c = getchar();
  if (c == '-') f = -1, c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * f;
}
namespace Flow {
const int N = 1e4 + 10, M = 1e5 + 10, inf = 1e9;
int tot, first[N], to[M << 1], flow[M << 1], last[M << 1];
inline void init() { tot = -1, memset((first), (-1), sizeof(first)); }
inline void add(int x, int y, int z) {
  to[++tot] = y, flow[tot] = z, last[tot] = first[x], first[x] = tot;
}
inline void Add(int x, int y, int z) { add(x, y, z), add(y, x, 0); }
int hd, tl, q[N], deep[N];
inline bool bfs(int s, int t, int n) {
  for (register int i = (1); i <= (n); i++) deep[i] = 0;
  hd = 0, q[tl = 1] = s, deep[s] = 1;
  while (hd < tl) {
    int u = q[++hd];
    for (int i = first[u]; i != -1; i = last[i])
      if (!deep[to[i]] && flow[i]) deep[q[++tl] = to[i]] = deep[u] + 1;
  }
  return deep[t];
}
int cur[N];
inline void init(int n) {
  for (register int i = (1); i <= (n); i++) cur[i] = first[i];
}
inline int dfs(int u, int t, int dist) {
  if (u == t || !dist) return dist;
  int Flow = 0, f;
  for (int i = cur[u]; i != -1; i = last[i]) {
    cur[u] = i;
    if (deep[to[i]] == deep[u] + 1 && (f = dfs(to[i], t, min(dist, flow[i])))) {
      dist -= f, Flow += f, flow[i] -= f, flow[i ^ 1] += f;
      if (!dist) break;
    }
  }
  return Flow;
}
inline void init2() {
  for (int i = 0; i <= tot; i += 2) flow[i] += flow[i + 1], flow[i + 1] = 0;
}
inline int Dinic(int s, int t, int n) {
  init2();
  int ans = 0;
  while (bfs(s, t, n)) init(n), ans += dfs(s, t, inf);
  return ans;
}
}  // namespace Flow
const int N = 210, inf = 1e9;
int n, m;
vector<pair<int, int> > e[N];
inline void Add(int x, int y, int z) {
  e[x].emplace_back(y, z), e[y].emplace_back(x, z);
}
int ans;
inline void Build(vector<int> v) {
  if (((int)(v).size()) <= 1) return;
  int x = v[0], y = v[1], z = Flow::Dinic(x, y, n);
  Add(x, y, z), ans += z;
  vector<int> l, r;
  for (auto i : v) {
    if (Flow::deep[i])
      l.push_back(i);
    else
      r.push_back(i);
  }
  Build(l), Build(r);
}
bool vis[N];
pair<int, pair<int, int> > mn;
inline void dfs(int u, int fa) {
  for (auto [v, w] : e[u])
    if (v != fa && vis[v]) {
      dfs(v, u), mn = min(mn, {w, {u, v}});
    }
}
inline void dfs(int u, int fa, vector<int> &vec) {
  vec.push_back(u);
  for (auto [v, w] : e[u])
    if (v != fa && vis[v]) {
      dfs(v, u, vec);
    }
}
inline void solve(vector<int> v) {
  if (((int)(v).size()) == 1) return printf("%d ", v[0]), void(0);
  for (auto i : v) vis[i] = 1;
  mn = {inf, {0, 0}}, dfs(v[0], 0);
  vector<int> l, r;
  dfs(mn.second.first, mn.second.second, l),
      dfs(mn.second.second, mn.second.first, r);
  for (auto i : v) vis[i] = 0;
  solve(l), solve(r);
}
int main() {
  Flow::init();
  n = read(), m = read();
  for (register int i = (1); i <= (m); i++) {
    int x = read(), y = read(), z = read();
    Flow::Add(x, y, z), Flow::Add(y, x, z);
  }
  vector<int> v;
  for (register int i = (1); i <= (n); i++) v.push_back(i);
  Build(v);
  printf("%d\n", ans);
  solve(v);
}
