#include <bits/stdc++.h>
using namespace std;
int n, m;
int head[205], p;
struct edge {
  int from, to, next, f;
} e[5005];
void addedge(int u, int v, int f) {
  e[p].to = v;
  e[p].f = f;
  e[p].next = head[u];
  head[u] = p++;
  e[p].to = u;
  e[p].f = 0;
  e[p].next = head[v];
  head[v] = p++;
}
void addedge2(int u, int v, int f) {
  e[p].from = u;
  e[p].to = v;
  e[p].f = f;
  e[p].next = head[u];
  head[u] = p++;
  e[p].from = v;
  e[p].to = u;
  e[p].f = f;
  e[p].next = head[v];
  head[v] = p++;
}
int dis[205], vis[205];
bool bfs(int s, int t) {
  memset(dis, 0, sizeof(dis));
  memset(vis, 0, sizeof(vis));
  queue<int> q;
  q.push(s);
  dis[s] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = 1;
    for (int i = head[u]; ~i; i = e[i].next) {
      int v = e[i].to, f = e[i].f;
      if (f && !dis[v]) {
        dis[v] = dis[u] + 1;
        q.push(v);
      }
    }
  }
  return dis[t] != 0;
}
int dfs(int u, int maxf, int t) {
  if (u == t) {
    return maxf;
  }
  int tmp = 0;
  for (int i = head[u]; ~i && tmp < maxf; i = e[i].next) {
    int v = e[i].to, f = e[i].f;
    if (f && dis[v] == dis[u] + 1) {
      f = dfs(v, min(maxf - tmp, f), t);
      tmp += f;
      e[i].f -= f;
      e[i ^ 1].f += f;
    }
  }
  if (!tmp) {
    dis[u] = 0;
  }
  return tmp;
}
int dinic(int s, int t) {
  int ans = 0;
  while (bfs(s, t)) {
    ans += dfs(s, 1000000000, t);
  }
  return ans;
}
int fa[205], w[205][205];
int mincut_tree() {
  int ans = 0;
  for (int i = 2; i <= n; i++) {
    fa[i] = 1;
  }
  for (int i = 2; i <= n; i++) {
    for (int j = 0; j < p; j += 2) {
      e[j].f += e[j ^ 1].f, e[j ^ 1].f = 0;
    }
    int k = dinic(i, fa[i]);
    ans += k;
    w[i][fa[i]] = w[fa[i]][i] = k;
    for (int j = i + 1; j <= n; j++) {
      if (vis[j] && fa[j] == fa[i]) {
        fa[j] = i;
      }
    }
  }
  memset(e, 0, sizeof(e));
  memset(head, -1, sizeof(head));
  p = 0;
  for (int i = 2; i <= n; i++) {
    addedge2(i, fa[i], w[i][fa[i]]);
  }
  return ans;
}
int minedge;
void findmin(int u, int fa) {
  for (int i = head[u]; ~i; i = e[i].next) {
    int v = e[i].to, f = e[i].f;
    if (v == fa || f == -1) {
      continue;
    }
    if (e[i].f < e[minedge].f) {
      minedge = i;
    }
    findmin(v, u);
  }
}
void solve(int x) {
  e[p + 1].f = 1000000000;
  minedge = p + 1;
  findmin(x, 0);
  int t = minedge;
  if (t == p + 1) {
    printf("%d ", x);
    return;
  }
  e[t].f = e[t ^ 1].f = -1;
  solve(e[t].from);
  solve(e[t].to);
}
int main() {
  scanf("%d%d", &n, &m);
  memset(head, -1, sizeof(head));
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    addedge(u, v, w);
    addedge(v, u, w);
  }
  printf("%d\n", mincut_tree());
  solve(1);
  return 0;
}
