#include <bits/stdc++.h>
using namespace std;
const int N = 205, M = 4005, inf = 2e8;
struct sub {
  int x, y, z;
} e[M];
int b[N];
int n, m, id[N], dep[N], S, T, head[N], nxt[M], to[M], dis[M];
int num = 1, ans = 0, Head[N], NUM = 1, TO[M], DIS[M] = {inf}, NXT[M];
inline void link(int x, int y, int z) {
  nxt[++num] = head[x];
  to[num] = y;
  head[x] = num;
  dis[num] = z;
  nxt[++num] = head[y];
  to[num] = x;
  head[y] = num;
  dis[num] = z;
}
inline void Link(int x, int y, int z) {
  NXT[++NUM] = Head[x];
  TO[NUM] = y;
  Head[x] = NUM;
  DIS[NUM] = z;
  NXT[++NUM] = Head[y];
  TO[NUM] = x;
  Head[y] = NUM;
  DIS[NUM] = z;
}
inline bool bfs() {
  queue<int> Q;
  memset(dep, 0, sizeof(dep));
  dep[S] = 1;
  Q.push(S);
  while (!Q.empty()) {
    int x = Q.front();
    Q.pop();
    for (int i = head[x]; i; i = nxt[i]) {
      int u = to[i];
      if (dep[u] || dis[i] <= 0) continue;
      dep[u] = dep[x] + 1;
      Q.push(u);
    }
  }
  return dep[T];
}
inline int dfs(int x, int flow) {
  if (x == T || !flow) return flow;
  int u, tmp, tot = 0;
  for (int i = head[x]; i; i = nxt[i]) {
    u = to[i];
    if (dep[u] != dep[x] + 1 || dis[i] <= 0) continue;
    tmp = dfs(u, min(flow, dis[i]));
    dis[i] -= tmp;
    dis[i ^ 1] += tmp;
    flow -= tmp;
    tot += tmp;
    if (!flow) break;
  }
  if (!tot) dep[x] = -1;
  return tot;
}
inline int maxflow(int tx, int ty) {
  S = tx;
  T = ty;
  int tot = 0, t;
  while (bfs()) {
    t = dfs(S, inf);
    while (t) tot += t, t = dfs(S, inf);
  }
  return tot;
}
inline void Clear() {
  memset(head, 0, sizeof(head));
  num = 1;
}
inline void solve(int l, int r) {
  if (l == r) return;
  Clear();
  for (int i = 1; i <= m; i++) link(e[i].x, e[i].y, e[i].z);
  int t = maxflow(id[l], id[r]), L = l - 1, R = r + 1;
  ans += t;
  Link(id[l], id[r], t);
  for (int i = l; i <= r; i++)
    if (dep[id[i]])
      b[++L] = id[i];
    else
      b[--R] = id[i];
  reverse(b + L + 1, b + R + 1);
  for (int i = l; i <= r; i++) id[i] = b[i];
  solve(l, L);
  solve(R, r);
}
bool vis[M];
int maxid = 0;
inline void BFS(int x, int last) {
  for (int i = Head[x]; i; i = NXT[i]) {
    if (TO[i] == last || vis[i]) continue;
    if (DIS[i] < DIS[maxid]) maxid = i;
    BFS(TO[i], x);
  }
}
inline void Deal(int x) {
  maxid = 0;
  BFS(x, x);
  if (maxid == 0) {
    printf("%d ", x);
    return;
  }
  vis[maxid] = vis[maxid ^ 1] = 1;
  int u = TO[maxid], v = TO[maxid ^ 1];
  Deal(u);
  Deal(v);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].z);
  for (int i = 1; i <= n; i++) id[i] = i;
  solve(1, n);
  printf("%d\n", ans);
  Deal(1);
  return 0;
}
