#include <bits/stdc++.h>
using namespace std;
inline long long rd() {
  long long x = 0;
  int ch = getchar(), f = 1;
  while (!isdigit(ch) && ch != '-') ch = getchar();
  if (ch == '-') f = -1, ch = getchar();
  while (isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
  return x * f;
}
inline void rt(long long x) {
  if (x < 0)
    putchar('-'), rt(-x);
  else if (x < 10)
    putchar('0' + x);
  else
    rt(x / 10), putchar('0' + x % 10);
}
const int maxn = 205, maxm = 2005;
int n, m, ins[maxn], ans = 0;
struct flowgragh {
  int to[maxm], nx[maxm], hd[maxn], cnt, cap[maxm];
  flowgragh() { memset(hd, -1, sizeof hd); }
  void addedge(int u, int v, int w) {
    to[cnt] = v;
    nx[cnt] = hd[u];
    cap[cnt] = w;
    hd[u] = cnt++;
    to[cnt] = u;
    nx[cnt] = hd[v];
    cap[cnt] = w;
    hd[v] = cnt++;
  }
  void init() {
    for (int i = 0; i < cnt; i += 2)
      cap[i] = cap[i ^ 1] = (cap[i] + cap[i ^ 1]) >> 1;
  }
  int S, T, dist[maxn], head, tail, que[maxn];
  bool bfs() {
    head = 1, tail = 0, que[++tail] = S;
    memset(dist, -1, sizeof dist);
    dist[S] = 1;
    while (head <= tail) {
      int u = que[head++];
      for (int i = hd[u]; ~i; i = nx[i]) {
        int v = to[i];
        if (dist[v] == -1 && cap[i]) {
          dist[v] = dist[u] + 1;
          if (v == T) return 1;
          que[++tail] = v;
        }
      }
    }
    return 0;
  }
  int dfs(int u, int flow) {
    if (u == T || !flow) return flow;
    int ret = 0, f;
    for (int i = hd[u]; ~i; i = nx[i]) {
      int v = to[i];
      if (dist[v] == dist[u] + 1 && (f = dfs(v, min(flow, cap[i])))) {
        ret += f, flow -= f;
        cap[i] -= f, cap[i ^ 1] += f;
        if (!flow) break;
      }
    }
    if (!ret) dist[u] = -1;
    return ret;
  }
  int dinic() {
    int ret = 0;
    while (bfs()) ret += dfs(S, 500000000);
    return ret;
  }
  void dfs(int u) {
    ins[u] = 1;
    for (int i = hd[u]; ~i; i = nx[i]) {
      int v = to[i];
      if (cap[i] && !ins[v]) dfs(v);
    }
  }
} fg;
int a[maxn], tmp[maxn];
struct tree {
  int len[maxn << 1], to[maxn << 1], nx[maxn << 1], hd[maxn], cnt;
  tree() { memset(hd, -1, sizeof hd); }
  void addedge(int u, int v, int w) {
    to[cnt] = v;
    nx[cnt] = hd[u];
    len[cnt] = w;
    hd[u] = cnt++;
    to[cnt] = u;
    nx[cnt] = hd[v];
    len[cnt] = w;
    hd[v] = cnt++;
  }
  int a[maxn], tmp[maxn], mark[maxn], del[maxn << 1];
  void dfs(int u) {
    mark[u] = 1;
    for (int i = hd[u]; ~i; i = nx[i]) {
      if (del[i]) continue;
      int v = to[i];
      if (!mark[v]) dfs(v);
    }
  }
  void printpath(int l, int r) {
    if (l == r) {
      printf("%d ", a[l]);
      return;
    }
    int mn = -1;
    for (int i = int(l); i <= int(r); i++) {
      for (int j = hd[a[i]]; ~j; j = nx[j]) {
        if (del[j]) continue;
        if (mn == -1 || len[j] < len[mn]) mn = j;
      }
    }
    del[mn] = del[mn ^ 1] = 1;
    memset(mark, 0, sizeof mark);
    dfs(to[mn]);
    int L = l, R = r;
    for (int i = int(l); i <= int(r); i++)
      if (mark[a[i]])
        tmp[L++] = a[i];
      else
        tmp[R--] = a[i];
    for (int i = int(l); i <= int(r); i++) a[i] = tmp[i];
    printpath(l, L - 1), printpath(R + 1, r);
  }
} t;
void solve(int l, int r) {
  if (l == r) return;
  fg.init();
  fg.S = a[l], fg.T = a[r];
  int ret = fg.dinic();
  ans += ret;
  t.addedge(a[l], a[r], ret);
  memset(ins, 0, sizeof ins);
  fg.dfs(a[l]);
  int L = l, R = r;
  for (int i = int(l); i <= int(r); i++)
    if (ins[a[i]])
      tmp[L++] = a[i];
    else
      tmp[R--] = a[i];
  for (int i = int(l); i <= int(r); i++) a[i] = tmp[i];
  solve(l, L - 1), solve(R + 1, r);
}
int main() {
  n = rd(), m = rd();
  for (int i = int(1); i <= int(m); i++) {
    int u = rd(), v = rd(), w = rd();
    fg.addedge(u, v, w);
  }
  for (int i = int(1); i <= int(n); i++) a[i] = i;
  solve(1, n);
  rt(ans), putchar('\n');
  for (int i = int(1); i <= int(n); i++) t.a[i] = i;
  t.printpath(1, n);
}
