#include <bits/stdc++.h>
using namespace std;
template <typename T>
void read(T& n) {
  char ch;
  int sign = 1;
  while (!isdigit(ch = getchar()))
    if (ch == '-') sign = -1;
  n = ch - '0';
  while (isdigit(ch = getchar())) n = n * 10 + ch - '0';
  n *= sign;
}
const int INF = 1e9 + 7;
const int N = 211;
int n, m, l, r, first, s, t;
int a[N], d[N], vis[N * N], ans[N], tmp[N];
struct edge {
  int to, nxt, f;
} g[N * N], tr[N * N];
int ghead[N], gtail(1), thead[N], ttail(1);
void add(int l, int r, int first) {
  g[++gtail] = (edge){r, ghead[l], first}, ghead[l] = gtail;
}
void add2(int l, int r, int c) {
  tr[++ttail] = (edge){r, thead[l], c}, thead[l] = ttail;
}
bool bfs(int s, int t) {
  queue<int> que;
  que.push(s);
  for (int i = (1); i <= (n); ++i) d[i] = 0;
  d[s] = 1;
  while (!que.empty()) {
    int h = que.front();
    que.pop();
    for (int p = ghead[h]; p; p = g[p].nxt) {
      int v = g[p].to;
      if (!g[p].f) continue;
      if (!d[v]) d[v] = d[h] + 1, que.push(v);
    }
  }
  return d[t];
}
int dfs(int s, int t, int lim) {
  if (s == t) return lim;
  int ans = 0;
  for (int p = ghead[s]; p && lim; p = g[p].nxt) {
    int v = g[p].to;
    if (!g[p].f || d[v] != d[s] + 1) continue;
    int f = dfs(v, t, min(lim, g[p].f));
    g[p].f -= f, g[p ^ 1].f += f, lim -= f, ans += f;
  }
  return ans;
}
void belong(int first) {
  vis[first] = 1;
  for (int p = ghead[first]; p; p = g[p].nxt) {
    int v = g[p].to;
    if (g[p].f && !vis[v]) belong(v);
  }
}
void solve(int l, int r) {
  if (l >= r) return;
  s = a[l], t = a[r];
  int flow = 0;
  for (int i = 2; i <= gtail; i += 2)
    g[i].f = g[i + 1].f = (g[i].f + g[i + 1].f) >> 1;
  while (bfs(s, t)) flow += dfs(s, t, INF);
  memset(vis, 0, sizeof(vis));
  belong(s);
  add2(s, t, flow), add2(t, s, flow);
  int i = l - 1, j = r + 1;
  for (int k = (l); k <= (r); ++k) tmp[k] = a[k];
  for (int k = (l); k <= (r); ++k)
    if (vis[tmp[k]])
      a[++i] = tmp[k];
    else
      a[--j] = tmp[k];
  solve(l, i), solve(j, r);
}
int scan(int first, int fa) {
  int ret = 1;
  for (int p = thead[first]; p; p = tr[p].nxt) {
    int v = tr[p].to;
    if (vis[p] || v == fa) continue;
    ret += scan(v, first);
  }
  return ret;
}
void dfs2(int first, int fa, int& mi, int& s, int& t) {
  for (int p = thead[first]; p; p = tr[p].nxt) {
    int v = tr[p].to;
    if (v == fa || vis[p]) continue;
    if (tr[p].f < mi) mi = tr[p].f, s = first, t = p;
    dfs2(v, first, mi, s, t);
  }
}
void divide(int l, int r, int rt) {
  if (l == r) {
    ans[l] = rt;
    return;
  }
  int mi = INF, first, t;
  dfs2(rt, 0, mi, first, t);
  vis[t] = vis[t ^ 1] = 1;
  int sl = scan(first, 0), sr = scan(tr[t].to, 0);
  divide(l, l + sl - 1, first), divide(r - sr + 1, r, tr[t].to);
}
int main() {
  read(n), read(m);
  for (int i = (1); i <= (m); ++i) {
    read(l), read(r), read(first);
    add(l, r, first), add(r, l, first);
  }
  for (int i = (1); i <= (n); ++i) a[i] = i;
  solve(1, n);
  int ret = 0;
  for (int i = (1); i <= (n); ++i)
    for (int p = thead[i]; p; p = tr[p].nxt) ret += tr[p].f;
  printf("%d\n", ret / 2);
  memset(vis, 0, sizeof(vis)), divide(1, n, 1);
  for (int i = (1); i <= (n); ++i) printf("%d%c", ans[i], " \n"[i == n]);
  return 0;
}
