#include <bits/stdc++.h>
using namespace std;
namespace MF {
using flow_t = int;
const int N = 205, M = 1e3 + 5, inf = 1e9;
int cnt, head[N];
struct edge {
  int next, to, w, fw;
} e[M << 1];
inline void addedge(int u, int v, int w) {
  e[++cnt] = {head[u], v, w, 0};
  head[u] = cnt;
}
int n, s, t, d[N], cur[N];
flow_t maxflow;
void init(int _n) {
  n = _n;
  cnt = 1, maxflow = 0;
  memset(head, 0, (n + 1) << 2);
}
void add(int u, int v, int cap) { addedge(u, v, cap), addedge(v, u, cap); }
bool bfs() {
  memset(d, 0, (n + 1) << 2);
  memcpy(cur, head, (n + 1) << 2);
  queue<int> q;
  q.push(s);
  d[s] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = head[u]; i; i = e[i].next) {
      int v = e[i].to;
      if (e[i].fw < e[i].w && !d[v]) {
        d[v] = d[u] + 1;
        if (v == t) return 1;
        q.push(v);
      }
    }
  }
  return 0;
}
int dfs(int u, int flow) {
  if (u == t) return flow;
  int res = flow;
  for (int &i = cur[u]; i; i = e[i].next) {
    int v = e[i].to;
    if (e[i].fw < e[i].w && d[v] == d[u] + 1) {
      int low = dfs(v, min(flow, e[i].w - e[i].fw));
      if (low) {
        e[i].fw += low, e[i ^ 1].fw -= low;
        flow -= low;
        if (!flow) break;
      } else
        d[v] = -1;
    }
  }
  return res - flow;
}
int go(int x, int y) {
  maxflow = 0;
  s = x, t = y;
  for (int i = 2; i <= cnt; i++) e[i].fw = 0;
  while (bfs()) maxflow += dfs(s, inf);
  return maxflow;
}
}  // namespace MF
int n, m;
struct GHT {
  static const int N = 205;
  int pt[N], tmpt[N], ans;
  int vis[N], dfn;
  int mn, a, b, G[N][N];
  void dfs(int u) {
    vis[u] = dfn;
    for (int i = MF::head[u]; i; i = MF::e[i].next)
      if (MF::e[i].fw < MF::e[i].w && vis[MF::e[i].to] != dfn) dfs(MF::e[i].to);
  }
  void build(int l, int r) {
    if (l >= r) return;
    int x = pt[l], y = pt[l + 1];
    int cutw = MF::go(x, y);
    G[x][y] = G[y][x] = cutw;
    ans += cutw;
    ++dfn;
    dfs(x);
    int p = l, q = r;
    for (int i = l; i <= r; i++)
      if (vis[pt[i]] == dfn)
        tmpt[p++] = pt[i];
      else
        tmpt[q--] = pt[i];
    for (int i = l; i <= r; i++) pt[i] = tmpt[i];
    build(l, p - 1);
    build(q + 1, r);
  }
  void run() {
    iota(pt + 1, pt + n + 1, 1);
    for (int i = 1; i <= n; i++)
      for (int j = 1; j <= n; j++) G[i][j] = -1;
    build(1, n);
  }
  void getmn(int u, int fa) {
    for (int v = 1; v <= n; v++) {
      if (G[u][v] == -1 || v == fa) continue;
      if (G[u][v] < mn) mn = G[u][v], a = u, b = v;
      getmn(v, u);
    }
  }
  void gao(int u) {
    mn = MF::inf;
    getmn(u, 0);
    if (mn == MF::inf) {
      printf("%d ", u);
      return;
    }
    int tmpa = a, tmpb = b;
    G[a][b] = G[b][a] = -1;
    gao(tmpa);
    gao(tmpb);
  }
} T;
int main() {
  scanf("%d%d", &n, &m);
  MF::init(n);
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    MF::add(u, v, w);
  }
  T.run();
  printf("%d\n", T.ans);
  T.gao(1);
  return 0;
}
