#include <bits/stdc++.h>
using namespace std;
template <class T>
void read(T& x) {
  char c = getchar();
  T p = 1, n = 0;
  while (c < '0' || c > '9') {
    if (c == '-') p = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    n = n * 10 + c - '0';
    c = getchar();
  }
  x = p * n;
}
template <class T, class U>
void read(T& x, U& y) {
  read(x), read(y);
}
template <class T, class U, class V>
void read(T& x, U& y, V& z) {
  read(x), read(y), read(z);
}
const int maxn = 200 + 5, maxm = 1000 + 5, INF = 0x3f3f3f3f;
namespace FLOW {
struct E {
  int v, n, f;
} e[maxm << 1];
int h[maxn], ec = 2;
inline void add_edge(int u, int v, int c) {
  e[ec] = (E){v, h[u], c}, h[u] = ec++, e[ec] = (E){u, h[v], c}, h[v] = ec++;
}
queue<int> Q;
int d[maxn], s, t;
bool bfs() {
  memset(d, INF, sizeof d);
  d[s] = 0;
  Q.push(s);
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v)
      if (e[i].f && d[v] == INF) d[v] = d[u] + 1, Q.push(v);
  }
  return d[t] != INF;
}
int cur[maxn];
int dfs(int u = s, int a = INF) {
  if (u == t || !a) return a;
  int flow = 0, f;
  for (int &i = cur[u], v = e[i].v; i; i = e[i].n, v = e[i].v)
    if (d[v] == d[u] + 1 && (f = dfs(v, min(a, e[i].f)))) {
      e[i].f -= f, e[i ^ 1].f += f, a -= f, flow += f;
      if (!a) break;
    }
  return flow;
}
}  // namespace FLOW
namespace TREE {
struct E {
  int v, n, w, f;
} e[maxn << 1];
int h[maxn], ec = 2;
inline void add_edge(int u, int v, int w) {
  e[ec] = (E){v, h[u], w, 0}, h[u] = ec++, e[ec] = (E){u, h[v], w, 0},
  h[v] = ec++;
}
int ti, w;
void dfs(int u, int f = 0) {
  for (int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v)
    if (!e[i].f && v != f) {
      dfs(v, u);
      if (e[i].w < w) w = e[i].w, ti = i;
    }
}
void dc(int u = 1) {
  ti = INF, w = INF;
  dfs(u);
  int i = ti;
  if (i == INF) {
    printf("%d ", u);
    return;
  }
  e[i].f = e[i ^ 1].f = true;
  dc(e[i].v);
  dc(e[i ^ 1].v);
}
}  // namespace TREE
bool f[maxn];
void go(int u) {
  f[u] = true;
  using namespace FLOW;
  for (int i = h[u], v = e[i].v; i; i = e[i].n, v = e[i].v)
    if (!f[v] && e[i].f) go(v);
}
int a[maxn], b[maxn], ret = 0;
void dc(int l, int r) {
  if (l == r) return;
  using namespace FLOW;
  for (int i = 2; i < ec; i += 2)
    e[i].f = e[i ^ 1].f = (e[i].f + e[i ^ 1].f) >> 1;
  s = a[l], t = a[r];
  int w = 0;
  while (bfs()) memcpy(cur, h, sizeof h), w += dfs();
  TREE::add_edge(s, t, w);
  ret += w;
  memset(f, false, sizeof f);
  go(s);
  int _l = l, _r = r;
  for (int i = l; i <= r; ++i)
    if (f[a[i]])
      b[_l++] = a[i];
    else
      b[_r--] = a[i];
  for (int i = l; i <= r; ++i) a[i] = b[i];
  dc(l, _l - 1), dc(_r + 1, r);
}
int main() {
  int n, m;
  read(n, m);
  int u, v, c;
  while (m--) read(u, v, c), FLOW::add_edge(u, v, c);
  for (int i = 1; i <= n; ++i) a[i] = i;
  dc(1, n);
  printf("%d\n", ret);
  TREE::dc();
  return 0;
}
