#include <bits/stdc++.h>
using namespace std;
const int N = 205;
struct E {
  int v, nxt, w, f;
} e[N * 10];
int n, m, cc = 1, sum, hd[N], dis[N], q[N], iter[N], c[N][N], ans[N];
inline void add(int u, int v, int w) {
  e[++cc] = (E){v, hd[u], w, w};
  hd[u] = cc;
}
inline bool bfs(int s, int t) {
  memcpy(iter, hd, sizeof(hd));
  memset(dis, -1, sizeof(dis));
  int l = 0, r = 0;
  q[++r] = s;
  dis[s] = 0;
  while (l < r) {
    int x = q[++l];
    for (int i = hd[x], y; i; i = e[i].nxt)
      if (e[i].w && dis[y = e[i].v] == -1) {
        dis[y] = dis[x] + 1;
        q[++r] = y;
      }
  }
  return ~dis[t];
}
int dfs(int x, int t, int f) {
  if (x == t || !f) return f;
  int sf = 0, y;
  for (int &i = iter[x]; i; i = e[i].nxt)
    if (e[i].w && dis[y = e[i].v] == dis[x] + 1) {
      int w = dfs(y, t, min(f, e[i].w));
      e[i].w -= w;
      e[i ^ 1].w += w;
      f -= w;
      sf += w;
      if (!f) break;
    }
  if (!f) dis[x] = -1;
  return sf;
}
int dinic(int s, int t) {
  for (int i = 2; i <= cc; i++) e[i].w = e[i].f;
  int ans = 0;
  while (bfs(s, t)) ans += dfs(s, t, 1e9);
  return ans;
}
void sol(vector<int> v) {
  if (v.size() == 1) return;
  int f = dinic(v[0], v[1]);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if ((dis[i] != -1) ^ (dis[j] != -1)) c[i][j] = min(c[i][j], f);
  vector<int> ls, rs;
  for (int i = 0; i < v.size(); i++)
    ~dis[v[i]] ? ls.push_back(v[i]) : rs.push_back(v[i]);
  sol(ls);
  sol(rs);
}
void gt(vector<int> v) {
  if (v.size() == 1) {
    ans[++ans[0]] = v[0];
    return;
  }
  int s = v[0], t = v[1];
  for (int i = 2; i < v.size(); i++)
    if (c[s][v[i]] < c[s][t]) t = v[i];
  sum += dinic(s, t);
  vector<int> ls, rs;
  for (int i = 0; i < v.size(); i++)
    ~dis[v[i]] ? ls.push_back(v[i]) : rs.push_back(v[i]);
  gt(ls);
  gt(rs);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, u, v, w; i <= m; i++) {
    scanf("%d%d%d", &u, &v, &w);
    add(u, v, w);
    add(v, u, w);
  }
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) c[i][j] = 1e9;
  vector<int> all;
  for (int i = 1; i <= n; i++) all.push_back(i);
  sol(all);
  gt(all);
  printf("%d\n", sum);
  for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
  return 0;
}
