#include <bits/stdc++.h>
const int N = 200;
const int inf = 1e9;
using namespace std;
struct edges {
  int u, v, w;
} edge[N + 5];
int n, m, t[N + 5], t1[N + 5], t2[N + 5], e1[N + 5], e2[N + 5], e[N + 5],
    edge_cnt, fa[N + 5], a[N + 5], ans;
namespace F {
const int N = 3e6;
const long long inf = 2e18;
struct edges {
  int to;
  long long cost;
} edge[N * 2 + 5], e[N * 2 + 5];
int nxt[N * 2 + 5], head[N + 5], edge_cnt = 1, dis[N + 5], q[N + 5], cur[N + 5],
                                 S, T;
void add_edge(int u, int v, long long w) {
  edge[++edge_cnt] = (edges){v, w};
  nxt[edge_cnt] = head[u];
  head[u] = edge_cnt;
}
void add(int u, int v, long long w) {
  add_edge(u, v, w);
  add_edge(v, u, w);
}
int bfs() {
  for (int i = 1; i <= n; i++) cur[i] = head[i], dis[i] = 0;
  int l = 1, r = 0;
  dis[S] = 1;
  q[++r] = S;
  while (l <= r) {
    int u = q[l++];
    for (int i = head[u]; i; i = nxt[i]) {
      int v = edge[i].to, w = edge[i].cost;
      if (w && !dis[v]) {
        dis[v] = dis[u] + 1;
        q[++r] = v;
      }
    }
  }
  return dis[T];
}
long long dfs(int u, long long flow) {
  if (u == T) return flow;
  long long sm = 0;
  for (int &i = cur[u]; i; i = nxt[i]) {
    int v = edge[i].to;
    long long w = edge[i].cost;
    if (dis[v] == dis[u] + 1 && w) {
      long long res = dfs(v, min(w, flow));
      edge[i].cost -= res;
      edge[i ^ 1].cost += res;
      sm += res;
      flow -= res;
      if (!flow) break;
    }
  }
  return sm;
}
void init() {
  for (int i = 2; i <= edge_cnt; i++) e[i] = edge[i];
}
void clear() {
  for (int i = 2; i <= edge_cnt; i++) edge[i] = e[i];
}
long long dinic(int s, int t) {
  S = s;
  T = t;
  clear();
  long long ans = 0;
  while (bfs()) ans += dfs(S, inf);
  return ans;
}
}  // namespace F
int find(int x) {
  if (fa[x] == x) return x;
  return fa[x] = find(fa[x]);
}
void build(int l, int r) {
  if (l >= r) return;
  int val = F::dinic(t[l], t[r]), cnt1 = 0, cnt2 = 0;
  edge[++edge_cnt] = (edges){t[l], t[r], val};
  for (int i = l; i <= r; i++)
    if (F::dis[t[i]])
      t1[++cnt1] = t[i];
    else
      t2[++cnt2] = t[i];
  for (int i = 1; i <= cnt1; i++) t[i] = t1[i];
  for (int i = 1; i <= cnt2; i++) t[i + cnt1] = t2[i];
  build(1, cnt1);
  build(cnt1 + 1, cnt2 + cnt1);
}
void solve(int l, int r, int ql, int qr) {
  if (l > r) return;
  if (l == r) {
    a[l] = t[l];
    return;
  }
  for (int i = l; i <= r; i++) fa[t[i]] = t[i];
  int mi = inf, id = 0, cnt1 = 0, cnt2 = 0, q1 = 0, q2 = 0;
  for (int i = ql; i <= qr; i++)
    if (edge[e[i]].w < mi) mi = edge[e[i]].w, id = e[i];
  ans += mi;
  for (int i = ql; i <= qr; i++)
    if (e[i] != id) fa[find(edge[e[i]].u)] = find(edge[e[i]].v);
  int x = find(edge[id].u);
  for (int i = l; i <= r; i++) {
    if (find(t[i]) == x)
      t1[++cnt1] = t[i];
    else
      t2[++cnt2] = t[i];
  }
  for (int i = ql; i <= qr; i++)
    if (e[i] != id) {
      if (find(edge[e[i]].u) == x)
        e1[++q1] = e[i];
      else
        e2[++q2] = e[i];
    }
  for (int i = 1; i <= cnt1; i++) t[i + l - 1] = t1[i];
  for (int i = 1; i <= cnt2; i++) t[l + i + cnt1 - 1] = t2[i];
  for (int i = 1; i <= q1; i++) e[i + ql - 1] = e1[i];
  for (int i = 1; i <= q2; i++) e[i + q1 + ql - 1] = e2[i];
  solve(l, l + cnt1 - 1, ql, ql + q1 - 1);
  solve(l + cnt1, r, ql + q1, ql + q1 + q2 - 1);
}
int main() {
  scanf("%d%d", &n, &m);
  int u, v, w;
  for (int i = 1; i <= m; i++) {
    scanf("%d%d%d", &u, &v, &w);
    F::add(u, v, w);
  }
  F::init();
  for (int i = 1; i <= n; i++) t[i] = i;
  build(1, n);
  for (int i = 1; i <= n; i++) t[i] = i;
  for (int i = 1; i < n; i++) e[i] = i;
  solve(1, n, 1, n - 1);
  cout << ans << endl;
  for (int i = 1; i <= n; i++) printf("%d ", a[i]);
  return 0;
}
