#include <bits/stdc++.h>
int n, ans, m;
int p[207];
namespace Graph {
using namespace std;
const int maxn = 207;
const int maxm = 2007;
struct edge {
  int u, v, w;
  edge(int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w) {}
};
vector<int> G[maxn];
vector<edge> E;
int mx_val, mx_id;
int vis[maxn], used[maxm];
struct cmp {
  inline bool operator()(int a, int b) { return E[a].w < E[b].w; }
};
priority_queue<int, vector<int>, cmp> pq;
inline void ins(int u, int v, int w) {
  G[u].push_back(E.size());
  G[v].push_back(E.size());
  if (w > mx_val) mx_val = w, mx_id = E.size();
  E.push_back(edge(u, v, w));
}
inline void solve(int* p) {
  pq.push(mx_id);
  used[mx_id] = 1;
  int cnt = 0;
  while (cnt < n) {
    int x = pq.top();
    pq.pop();
    int u = E[x].u, v = E[x].v, t1 = 0, t2 = 0;
    if (!vis[u] && !vis[v]) {
      p[++cnt] = u, p[++cnt] = v;
      vis[u] = vis[v] = 1;
      t1 = t2 = 1;
    } else if (!vis[u]) {
      p[++cnt] = u;
      vis[u] = 1, t1 = 1;
    } else if (!vis[v]) {
      p[++cnt] = v;
      vis[v] = 1, t2 = 1;
    }
    if (t1)
      for (auto x : G[u])
        if (!used[x]) pq.push(x);
    if (t2)
      for (auto x : G[v])
        if (!used[x]) pq.push(x);
  }
}
}  // namespace Graph
namespace GomoryHuTree {
using namespace std;
const int maxn = 207;
const int maxm = 4007;
const int inf = 0x7fffffff;
typedef int arr[maxn];
typedef int adj[maxm];
int ett = 1, S, T;
arr head, cur, dis, belong;
adj to, nxt, cap, flow;
queue<int> Q;
inline void ins(int u, int v, int c) {
  to[++ett] = v, nxt[ett] = head[u], head[u] = ett, cap[ett] = c;
  to[++ett] = u, nxt[ett] = head[v], head[v] = ett, cap[ett] = 0;
}
int dfs(int u, int a) {
  if (u == T || !a) return a;
  int ret = 0, f;
  for (int& i = cur[u]; i; i = nxt[i]) {
    int v = to[i];
    if (dis[v] == dis[u] + 1 && (f = dfs(v, min(a, cap[i] - flow[i])))) {
      flow[i] += f, flow[i ^ 1] -= f, ret += f, a -= f;
      if (!a) break;
    }
  }
  return ret;
}
inline bool bfs() {
  for (int i = 1; i <= n; i++) dis[i] = 0;
  dis[S] = 1, Q.push(S);
  while (!Q.empty()) {
    int u = Q.front();
    Q.pop();
    for (int i = head[u]; i; i = nxt[i])
      if (cap[i] > flow[i]) {
        int v = to[i];
        if (!dis[v]) {
          dis[v] = dis[u] + 1;
          Q.push(v);
        }
      }
  }
  return dis[T] > 0;
}
inline int max_flow(int s, int t) {
  S = s, T = t;
  for (int i = 1; i <= n; i++) belong[i] = 0;
  for (int i = 1; i <= ett; i++) flow[i] = 0;
  int ret = 0;
  while (bfs()) {
    for (int i = 1; i <= n; i++) cur[i] = head[i];
    ret += dfs(S, inf);
  }
  return ret;
}
void dfs_s(int u) {
  belong[u] = 1;
  for (int i = head[u]; i; i = nxt[i])
    if (cap[i] > flow[i] && !belong[to[i]]) dfs_s(to[i]);
}
void build(vector<int>& dat) {
  if (dat.size() == 1) return;
  int t1 = dat[0], t2 = dat[1];
  int w = max_flow(t1, t2);
  Graph::ins(t1, t2, w);
  ::ans += w;
  dfs_s(t1);
  vector<int> l, r;
  for (auto v : dat)
    if (belong[v])
      l.push_back(v);
    else
      r.push_back(v);
  build(l), build(r);
}
inline void build() {
  vector<int> tmp;
  for (int i = 1; i <= n; i++) tmp.push_back(i);
  build(tmp);
}
}  // namespace GomoryHuTree
void input() {
  std::cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int u, v, c;
    std::cin >> u >> v >> c;
    GomoryHuTree::ins(u, v, c);
    GomoryHuTree::ins(v, u, c);
  }
}
void solve() {
  GomoryHuTree::build();
  printf("%d\n", ans);
  Graph::solve(p);
  for (int i = 1; i <= n; i++) printf("%d%c", p[i], i == n ? '\n' : ' ');
}
int main() {
  input();
  solve();
  return 0;
}
