#include <bits/stdc++.h>
using namespace std;
int N, M;
int S, T, pt, ans, w;
int mn[205][205];
int f[205][205], g[205][205];
int dis[205], sum[205];
int vis[205];
int q[205], tmd;
vector<int> all, out;
bool build(int S) {
  int h = 0, t = 1, i;
  q[1] = S;
  for (i = 1; i <= N; i++) dis[i] = -1;
  dis[S] = 0;
  while (h < t) {
    int x = q[++h];
    for (i = 1; i <= N; i++)
      if (f[x][i]) {
        int y = i;
        if (dis[y] < 0) dis[y] = dis[x] + 1, q[++t] = y;
        if (y == T) return 1;
      }
  }
  return 0;
}
int dinic(int x, int low) {
  if (x == T) return low;
  int w = 0, res, i;
  for (i = 1; i <= N; i++)
    if (f[x][i]) {
      int y = i;
      if (dis[y] == dis[x] + 1 && (res = dinic(y, min(low - w, f[x][i]))))
        f[x][i] -= res, f[i][x] += res, w += res;
    }
  if (!w) dis[x] = -1;
  return w;
}
void Query(int x, int fr) {
  int i, f1 = 0, r1 = 0;
  memset(dis, 0, sizeof(dis));
  q[++r1] = x, dis[x] = 1;
  while (f1 < r1) {
    x = q[++f1];
    for (i = 1; i <= N; i++)
      if (!dis[i] && f[x][i] && f[i][x]) {
        dis[i] = 1;
        q[++r1] = i;
      }
  }
}
void Work(vector<int> poly) {
  if (poly.size() < 2) return;
  int i, j, tmp, get = 0;
  int fr, to;
  vector<int> x, y;
  x.clear(), y.clear();
  memcpy(f, g, sizeof(f));
  memset(dis, 0, sizeof(dis));
  memset(sum, 0, sizeof(sum));
  pt = sum[0] = N;
  S = poly[0], T = poly[1];
  memset(vis, 0, sizeof(vis));
  while (build(S)) get += dinic(S, 0x7fffffff);
  for (i = 1; i <= N; i++) vis[i] = (dis[i] < 0);
  for (i = 1; i <= N; i++)
    if (vis[i])
      x.push_back(i);
    else
      y.push_back(i);
  for (i = 0; i < x.size(); i++)
    for (j = 0; j < y.size(); j++)
      mn[x[i]][y[j]] = mn[y[j]][x[i]] = min(mn[x[i]][y[j]], get);
  x.clear(), y.clear();
  for (i = 0; i < poly.size(); i++)
    if (vis[poly[i]])
      x.push_back(poly[i]);
    else
      y.push_back(poly[i]);
  Work(x), Work(y);
}
void Dfs(vector<int> all) {
  if (all.size() < 2) {
    out.push_back(all[0]);
    return;
  }
  int i, tmp, best = 0x7fffffff, get = 0;
  vector<int> x, y;
  x.clear(), y.clear();
  memset(vis, 0, sizeof(vis));
  T = all[all.size() - 1];
  for (i = 0; i < all.size() - 1; i++)
    if (mn[all[i]][T] < best) S = all[i], best = mn[S][T];
  memcpy(f, g, sizeof(f));
  memset(dis, 0, sizeof(dis)), memset(sum, 0, sizeof(sum));
  pt = sum[0] = N;
  memset(vis, 0, sizeof(vis));
  while (build(S)) get += dinic(S, 0x7fffffff);
  for (i = 1; i <= N; i++) vis[i] = (dis[i] < 0);
  ans += get;
  for (i = 0; i < all.size(); i++)
    if (vis[all[i]])
      x.push_back(all[i]);
    else
      y.push_back(all[i]);
  Dfs(x), Dfs(y);
}
int main() {
  int i, j;
  int fr, to, dts, get;
  srand(time(0));
  scanf("%d %d", &N, &M);
  for (i = 1; i <= M; i++) {
    scanf("%d %d %d", &fr, &to, &dts);
    f[fr][to] += dts, f[to][fr] += dts;
  }
  memcpy(g, f, sizeof(g));
  for (i = 1; i <= N; i++)
    for (j = 1; j <= N; j++) mn[i][j] = 0x7fffffff;
  for (i = 1; i <= N; i++) all.push_back(i);
  random_shuffle(all.begin(), all.end());
  memset(mn, 63, sizeof(mn));
  Work(all);
  Dfs(all);
  printf("%d\n", ans);
  for (i = 1; i <= N; i++) printf("%d%c", out[i - 1], (i == N) ? '\n' : ' ');
  return 0;
}
