#include <bits/stdc++.h>
using namespace std;
int a, b, t, n, m, f[100010], ans, trl;
struct node {
  int next, ar, flow, b;
} k[100010 * 20];
int first[100010], dis[100010], len;
int X[100010], y[100010], v[100010], e[100010];
int t1[100010], t2[100010], tl1, tl2, ANS;
void add(int a, int b, int t) {
  len++;
  k[len].ar = b;
  k[len].next = first[a];
  first[a] = len;
  k[len].flow = t;
}
int head, tail, d[100010];
bool bfs() {
  head = 0, tail = 1;
  d[0] = a;
  for (register int i = 1; i <= n; i++) dis[i] = 0;
  dis[a] = 1;
  while (head < tail) {
    t = d[head];
    head++;
    for (register int i = first[t]; i; i = k[i].next) {
      if (dis[k[i].ar] == 0 && k[i].flow > 0) {
        dis[k[i].ar] = dis[t] + 1;
        if (k[i].ar == b) return true;
        d[tail] = k[i].ar;
        tail++;
      }
    }
  }
  return false;
}
int dfs(int xx, int flow) {
  if (xx == b) return flow;
  if (flow == 0) return 0;
  if (dis[xx] >= dis[b]) return 0;
  int h, s = 0;
  for (register int i = first[xx]; i > 1; i = k[i].next) {
    if (flow == 0) {
      dis[xx] = 0;
      break;
    }
    if (dis[k[i].ar] == dis[xx] + 1 && k[i].flow > 0) {
      h = dfs(k[i].ar, min(flow, k[i].flow));
      s += h;
      flow -= h;
      k[i].flow -= h;
      k[i ^ 1].flow += h;
      if (h == 0) dis[k[i].ar] = 0;
    }
  }
  return s;
}
void dinic() {
  for (register int i = 1; i <= n; i++) first[i] = 0;
  len = 1, ans = 0;
  for (register int i = 1; i <= m; i++)
    add(X[i], y[i], f[i]), add(y[i], X[i], f[i]);
  while (bfs()) ans += dfs(a, 0x7ffffff);
}
struct gGomory_Hu_Tree {
  node tr[100010 * 2], trt[2][100010];
  int trl, first[100010];
  void adtr(int a, int b, int t) {
    trl++;
    tr[trl].ar = b;
    tr[trl].b = a;
    tr[trl].flow = t;
    tr[trl].next = first[a];
    first[a] = trl;
    ANS += t;
  }
  void dfs(int x, int y, int &w) {
    for (int i = first[x]; i; i = tr[i].next) {
      if (tr[i].flow >= 0 && tr[i].ar != y) {
        if (tr[i].flow < tr[w].flow) w = i;
        dfs(tr[i].ar, x, w);
      }
    }
  }
  void work(int x) {
    int t = 1;
    dfs(x, 0, t);
    if (t == 1) {
      printf("%d ", x);
      return;
    }
    tr[t].flow = tr[t ^ 1].flow = -1;
    work(tr[t].ar);
    work(tr[t].b);
  }
} ght;
void build(int l, int r) {
  if (l >= r) return;
  a = v[l];
  b = v[l + 1];
  dinic();
  ght.adtr(b, a, ans);
  ght.adtr(a, b, ans);
  int tl1 = 0, tl2 = 0;
  for (register int i = l; i <= r; i++) {
    if (dis[v[i]])
      tl1++, t1[tl1] = v[i], dis[v[i]] = 0;
    else
      tl2++, t2[tl2] = v[i];
  }
  for (register int i = 1; i <= tl1; i++) v[i + l - 1] = t1[i];
  for (register int i = 1; i <= tl2; i++) v[l + tl1 + i - 1] = t2[i];
  build(l, tl1 + l - 1);
  build(l + tl1, r);
}
int main() {
  int T;
  len = 1;
  scanf("%d%d", &n, &m);
  for (register int i = 1; i <= m; i++) {
    scanf("%d%d%d", &a, &b, &t);
    X[i] = a, y[i] = b, f[i] = t;
  }
  ght.trl = 1;
  ght.tr[1].flow = 0x3f3f3f3f;
  for (register int i = 1; i <= n; i++) v[i] = i;
  build(1, n);
  printf("%d\n", ANS / 2);
  ght.work(1);
  return 0;
}
