#include <bits/stdc++.h>
using namespace std;
int n, m, Q, p[210], ANS[210], cnt, A, B, totans, TOT;
int dis[210], S, T, ans, frm[210], rk[210];
struct info {
  int v, c;
  unsigned r;
};
vector<info> a[210];
struct node {
  int v, w, used;
  unsigned r;
};
vector<node> s[210];
template <typename T>
void chkmin(T &x, T y) {
  x = min(x, y);
}
template <typename T>
void chkmax(T &x, T y) {
  x = max(x, y);
}
template <typename T>
void read(T &x) {
  x = 0;
  int f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
}
int bfs() {
  static int q[210], l = 0, r = -1;
  for (int i = 0; i <= r; ++i) dis[q[i]] = 0;
  dis[S] = 1, q[l = r = 0] = S;
  while (l <= r) {
    int pos = q[l++];
    for (unsigned i = 0, si = a[pos].size(); i < si; ++i) {
      int to = a[pos][i].v, cap = a[pos][i].c;
      if (!dis[to] && cap)
        dis[to] = dis[pos] + 1, q[++r] = to, frm[to] = pos, rk[to] = i;
    }
  }
  return dis[T];
}
void clear() {
  for (int i = 1; i <= n; ++i)
    for (int j = 0, si = a[i].size(); j < si; ++j) {
      info cur = a[i][j];
      a[i][j].c = a[cur.v][cur.r].c = (a[i][j].c + a[cur.v][cur.r].c) / 2;
    }
}
void flow() {
  int pos = T;
  while (pos != S) {
    info &tmp = a[frm[pos]][rk[pos]];
    --tmp.c, ++a[pos][tmp.r].c;
    pos = frm[pos];
  }
}
void build(int l, int r) {
  if (l == r) return;
  clear();
  S = p[l], T = p[r];
  ans = 0;
  while (bfs()) {
    ++ans;
    flow();
  }
  s[S].push_back((node){T, ans, 0, (unsigned)s[T].size()});
  s[T].push_back((node){S, ans, 0, (unsigned)s[S].size() - 1});
  static int q[210];
  int ll = l - 1, rr = r + 1;
  for (int i = l; i <= r; ++i)
    if (dis[p[i]])
      q[++ll] = p[i];
    else
      q[--rr] = p[i];
  for (int i = l; i <= r; ++i) p[i] = q[i];
  build(l, ll);
  build(rr, r);
}
void dfs(int pos, int dad) {
  ++cnt;
  for (unsigned i = 0, si = s[pos].size(); i < si; ++i) {
    int son = s[pos][i].v, wth = s[pos][i].w;
    if (son != dad && !s[pos][i].used) {
      if (!A)
        A = pos, B = i;
      else {
        if (s[A][B].w > wth) A = pos, B = i;
      }
      dfs(son, pos);
    }
  }
}
void work(int pos) {
  cnt = 0, A = B = 0;
  dfs(pos, 0);
  if (cnt == 1) {
    ANS[++totans] = pos;
    return;
  }
  s[A][B].used = 1;
  s[s[A][B].v][s[A][B].r].used = 1;
  TOT += s[A][B].w;
  int L = A, R = s[A][B].v;
  work(L);
  work(R);
}
int main() {
  read(n), read(m);
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    read(u), read(v), read(w);
    if (u == v) continue;
    a[u].push_back((info){v, w, (unsigned)a[v].size()});
    a[v].push_back((info){u, w, (unsigned)a[u].size() - 1});
  }
  for (int i = 1; i <= n; ++i) p[i] = i;
  build(1, n);
  work(1);
  printf("%d\n", TOT);
  for (int i = 1; i <= n; ++i) printf("%d%c", ANS[i], " \n"[i == n]);
  return 0;
}
