#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char c = getchar();
  while (c != '-' && c < 48) c = getchar();
  if (c == '-') f = -1, c = getchar();
  while (c > 47) x = x * 10 + (c ^ 48), c = getchar();
  return f * x;
}
const int maxn = 2e2 + 7;
const int maxm = 2e4 + 7;
const int inf = 0x3f3f3f3f;
namespace Dinic {
int head[maxn], to[maxm], w[maxm], nxt[maxm], tot = 1;
int cur[maxn], level[maxn];
void add_edge(int u, int v, int c) {
  ++tot;
  to[tot] = v;
  w[tot] = c;
  nxt[tot] = head[u];
  head[u] = tot;
  ++tot;
  to[tot] = u;
  w[tot] = 0;
  nxt[tot] = head[v];
  head[v] = tot;
}
void init() {
  memset(head, 0, sizeof(head));
  tot = 1;
}
bool bfs(int s, int t) {
  memset(level, 0, sizeof(level));
  queue<int> q;
  q.push(s);
  level[s] = 1;
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; i; i = nxt[i]) {
      int v = to[i];
      if (!w[i] || level[v]) continue;
      level[v] = level[u] + 1;
      q.push(v);
    }
  }
  return level[t];
}
int dfs(int u, int t, int flow) {
  if (u == t || flow == 0) return flow;
  int f, res = 0;
  for (int &i = cur[u]; i; i = nxt[i]) {
    int v = to[i];
    if (level[v] == level[u] + 1 && (f = dfs(v, t, min(flow, w[i]))) > 0) {
      w[i] -= f;
      w[i ^ 1] += f;
      flow -= f;
      res += f;
      if (!flow) break;
    }
  }
  if (!res) level[u] = 0;
  return res;
}
int dinic(int s, int t) {
  for (int i = 2; i <= tot; i += 2) w[i] = w[i] + w[i ^ 1], w[i ^ 1] = 0;
  int res = 0;
  while (bfs(s, t)) memcpy(cur, head, sizeof(cur)), res += dfs(s, t, inf);
  return res;
}
}  // namespace Dinic
int ans;
int go[maxn], in[maxn];
struct Edge {
  int u, v, w;
  bool operator<(const Edge &rhs) const { return w > rhs.w; }
};
struct GomoryHu_Tree {
  static const int logn = 8;
  int n, p[maxn], p1[maxn];
  int head[maxn], nxt[maxn * 2], to[maxn * 2], w[maxn * 2], tot;
  int mi[maxn][logn], fa[maxn][logn], dep[maxn];
  Edge e[maxn];
  int be[maxn], fst[maxn], lst[maxn];
  int find(int a) { return be[a] == a ? a : be[a] = find(be[a]); }
  void link(int u, int v) {
    int x = find(u), y = find(v);
    be[x] = y;
    go[lst[y]] = fst[x];
    in[fst[x]] = 1;
    lst[y] = lst[x];
  }
  inline void add_edge(int u, int v, int c) {
    ++tot;
    to[tot] = v;
    w[tot] = c;
    nxt[tot] = head[u];
    head[u] = tot;
    ++tot;
    to[tot] = u;
    w[tot] = c;
    nxt[tot] = head[v];
    head[v] = tot;
    e[tot / 2] = (Edge){u, v, c};
  }
  void init(int n) {
    this->n = n;
    for (int i = 1; i <= n; ++i)
      fst[i] = lst[i] = be[i] = p[i] = i, head[i] = 0,
      memset(mi[i], inf, sizeof(mi[i]));
    tot = 0;
  }
  void build(int l, int r) {
    if (l == r) return;
    int u = p[l], v = p[r];
    int w = Dinic::dinic(u, v), m = l, m1 = r;
    add_edge(u, v, w);
    for (int i = l; i <= r; ++i) {
      if (Dinic::level[p[i]])
        p1[m++] = p[i];
      else
        p1[m1--] = p[i];
    }
    for (int i = l; i <= r; ++i) p[i] = p1[i];
    build(l, m1);
    build(m, r);
  }
  void solve() {
    sort(e + 1, e + n);
    for (int i = 1; i < n; ++i) {
      auto [u, v, w] = e[i];
      ans += w;
      link(u, v);
    }
  }
  void print() {
    printf("%d\n", ans);
    for (int i = 1; i <= n; ++i)
      if (!in[i]) {
        printf("%d", i);
        while (go[i]) printf(" %d", i = go[i]);
        puts("");
        break;
      }
  }
} GT;
int main() {
  int n = read(), m = read();
  for (int i = 1; i <= m; ++i) {
    int u = read(), v = read(), c = read();
    Dinic::add_edge(u, v, c);
    Dinic::add_edge(v, u, c);
  }
  GT.init(n);
  GT.build(1, n);
  GT.solve();
  GT.print();
}
