#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5, INF = 1e9;
int N, M, Q;
namespace Dinic {
struct node {
  int v, next, k;
} E[MAXN];
int cur[MAXN], head[MAXN], Elen = 1, S, T;
void add(int u, int v, int k) {
  ++Elen, E[Elen].v = v, E[Elen].next = head[u], head[u] = Elen, E[Elen].k = k;
}
void ADD(int u, int v, int k) { add(u, v, k), add(v, u, 0); }
void reset() {
  for (int i = 2; i < Elen; i += 2) {
    E[i].k += E[i ^ 1].k, E[i ^ 1].k = 0;
  }
}
int dis[MAXN];
queue<int> Q;
bool bfs() {
  for (int i = 1; i <= N; ++i) dis[i] = 0;
  dis[S] = 1, Q.push(S);
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (int i = head[u]; i; i = E[i].next)
      if (E[i].k && !dis[E[i].v]) {
        dis[E[i].v] = dis[u] + 1, Q.push(E[i].v);
      }
  }
  return dis[T];
}
int dfs(int u, int lim) {
  if (u == T || !lim) return lim;
  int flow = 0;
  for (int i = cur[u]; i; i = E[i].next) {
    cur[u] = head[u];
    if (dis[E[i].v] == dis[u] + 1) {
      int d = dfs(E[i].v, min(lim, E[i].k));
      if (d) {
        lim -= d, flow += d, E[i].k -= d, E[i ^ 1].k += d;
        if (!lim) return flow;
      }
    }
  }
  return flow;
}
int dinic(int u, int v) {
  reset(), S = u, T = v;
  int ans = 0;
  while (bfs()) {
    for (int i = 1; i <= N; ++i) cur[i] = head[i];
    ans += dfs(S, INF);
  }
  return ans;
}
};  // namespace Dinic
namespace GomoryHu_Tree {
struct node {
  int v, next, k;
} E[MAXN];
int head[MAXN], Elen = 1;
void add(int u, int v, int k) {
  ++Elen, E[Elen].v = v, E[Elen].next = head[u], head[u] = Elen, E[Elen].k = k;
}
int a[MAXN], x[MAXN], y[MAXN];
void build(int l, int r) {
  if (l == r) return;
  int k = Dinic::dinic(a[l], a[l + 1]);
  add(a[l], a[l + 1], k), add(a[l + 1], a[l], k);
  int xl = 0, yl = 0;
  for (int i = l; i <= r; ++i) {
    if (Dinic::dis[a[i]])
      x[++xl] = a[i];
    else
      y[++yl] = a[i];
  }
  int pos = l - 1;
  for (int i = 1; i <= xl; ++i) a[++pos] = x[i];
  for (int i = 1; i <= yl; ++i) a[++pos] = y[i];
  build(l, l + xl - 1), build(l + xl, r);
}
void build() {
  for (int i = 1; i <= N; ++i) a[i] = i;
  build(1, N);
}
int ret, retu, fa[MAXN], arr[MAXN], al;
long long ans;
void dfs(int u, int ff) {
  fa[u] = ff;
  for (int i = head[u]; i; i = E[i].next)
    if (E[i].k && E[i].v != ff) {
      if (E[i].k < ret) ret = E[i].k, retu = E[i].v;
      dfs(E[i].v, u);
    }
}
void solve(int u) {
  ret = INF, retu = 0, dfs(u, 0);
  if (ret == INF)
    arr[++al] = u;
  else {
    ans += ret;
    int tu = fa[retu], tv = retu;
    for (int i = head[fa[retu]]; i; i = E[i].next)
      if (E[i].v == retu) E[i].k = E[i ^ 1].k = 0;
    solve(tu), solve(tv);
  }
}
}  // namespace GomoryHu_Tree
int main() {
  scanf("%d%d", &N, &M);
  int u, v, k;
  for (int i = 1; i <= M; ++i)
    scanf("%d%d%d", &u, &v, &k), Dinic::ADD(u, v, k), Dinic::ADD(v, u, k);
  GomoryHu_Tree::build();
  GomoryHu_Tree::solve(1);
  printf("%lld\n", GomoryHu_Tree::ans);
  for (int i = 1; i <= N; ++i) printf("%d ", GomoryHu_Tree::arr[i]);
  return 0;
}
