#include <bits/stdc++.h>
using namespace std;
const int N = 205;
struct edge {
  int to, next, f, wzp;
} e[N * 10];
int head[N], dis[N], q[N];
int cur[N], c[N][N], ans[N];
int n, m, S, T, tot = 1, sum;
void add(int x, int y, int v) {
  e[++tot] = (edge){y, head[x], v, v};
  head[x] = tot;
}
bool bfs() {
  for (int i = (1); i <= (int)n; i++) dis[i] = -1;
  int h = 0, t = 1;
  dis[S] = 0;
  q[1] = S;
  while (h != t) {
    int x = q[++h];
    for (int i = head[x]; i; i = e[i].next)
      if (dis[e[i].to] == -1 && e[i].f) {
        dis[e[i].to] = dis[x] + 1;
        if (e[i].to == T) return 1;
        q[++t] = e[i].to;
      }
  }
  return 0;
}
int dfs(int x, int flow) {
  if (x == T) return flow;
  int rest = flow, k;
  for (int &i = cur[x]; i && rest; i = e[i].next)
    if (e[i].f && dis[e[i].to] == dis[x] + 1) {
      k = dfs(e[i].to, min(e[i].f, rest));
      rest -= k;
      e[i].f -= k;
      e[i ^ 1].f += k;
    }
  if (rest) dis[x] = -1;
  return flow - rest;
}
int run() {
  for (int i = (2); i <= (int)tot; i++) e[i].f = e[i].wzp;
  int ans = 0;
  while (bfs()) {
    memcpy(cur, head, sizeof(cur));
    ;
    ans += dfs(S, 1e9);
  }
  return ans;
}
void work(vector<int> v) {
  if (v.size() == 1) return;
  S = v[0];
  T = v[1];
  int tmp = run();
  for (int i = (1); i <= (int)n; i++)
    for (int j = (1); j <= (int)n; j++)
      if ((dis[i] != -1) ^ (dis[j] != -1)) c[i][j] = min(c[i][j], tmp);
  vector<int> ls, rs;
  for (int i = (0); i <= (int)v.size() - 1; i++)
    dis[v[i]] != -1 ? ls.push_back(v[i]) : rs.push_back(v[i]);
  work(ls);
  work(rs);
}
void getans(vector<int> v) {
  if (v.size() == 1) return ans[++*ans] = v[0], void(0);
  S = v[0], T = v[1];
  for (int i = (2); i <= (int)v.size() - 1; i++)
    if (c[S][v[i]] < c[S][T]) T = v[i];
  sum += run();
  vector<int> ls, rs;
  for (int i = (0); i <= (int)v.size() - 1; i++)
    dis[v[i]] != -1 ? ls.push_back(v[i]) : rs.push_back(v[i]);
  getans(ls);
  getans(rs);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = (1); i <= (int)m; i++) {
    int x, y, v;
    scanf("%d%d%d", &x, &y, &v);
    add(x, y, v);
    add(y, x, v);
  }
  for (int i = (1); i <= (int)n; i++)
    for (int j = (1); j <= (int)n; j++) c[i][j] = 1e9;
  vector<int> all;
  for (int i = (1); i <= (int)n; i++) all.push_back(i);
  work(all);
  getans(all);
  printf("%d\n", sum);
  for (int i = (1); i <= (int)n; i++) printf("%d\n", ans[i]);
}
