#include <bits/stdc++.h>
using namespace std;
inline char nc() {
  return getchar();
  static char buf[100000], *l = buf, *r = buf;
  return l == r && (r = (l = buf) + fread(buf, 1, 100000, stdin), l == r)
             ? EOF
             : *l++;
}
template <class T>
void read(T &x) {
  x = 0;
  int f = 1, ch = nc();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = nc();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 - '0' + ch;
    ch = nc();
  }
  x *= f;
}
const int inf = 1e9;
const int maxn = 200 + 5;
int n, m, an;
int st, ed;
vector<int> P;
struct node {
  int to, cap, flow, rev;
  node(int to = 0, int cap = 0, int flow = 0, int rev = 0)
      : to(to), cap(cap), flow(flow), rev(rev) {}
};
vector<node> adj[maxn];
inline void addedge(int u, int v, int c) {
  adj[u].push_back(node(v, c, 0, adj[v].size()));
  adj[v].push_back(node(u, c, 0, adj[u].size() - 1));
}
void edge_init() {
  for (int u = 1; u <= n; ++u) {
    for (unsigned int i = 0; i < adj[u].size(); ++i) {
      adj[u][i].flow = 0;
    }
  }
}
namespace dinic {
unsigned int cur[maxn];
int dis[maxn];
bool bfs() {
  static int q[maxn];
  int hd = 0, tl = 0;
  memset(dis, -1, sizeof(dis));
  dis[st] = 0;
  q[tl++] = st;
  while (hd < tl) {
    int u = q[hd++];
    for (unsigned int i = 0; i < adj[u].size(); ++i) {
      node &e = adj[u][i];
      if (e.cap == e.flow) continue;
      if (dis[e.to] == -1) {
        dis[e.to] = dis[u] + 1;
        q[tl++] = e.to;
      }
    }
  }
  return dis[ed] != -1;
}
int dfs(int u, int flow) {
  if (u == ed || flow == 0) return flow;
  int rec = flow;
  for (unsigned int &i = cur[u]; i < adj[u].size(); ++i) {
    node &e = adj[u][i];
    if (dis[e.to] != dis[u] + 1) continue;
    int d = dfs(e.to, min(flow, e.cap - e.flow));
    e.flow += d;
    adj[e.to][e.rev].flow -= d;
    flow -= d;
    if (flow == 0) break;
  }
  return rec - flow;
}
int maxflow() {
  int flow = 0;
  while (bfs()) {
    memset(cur, 0, sizeof(cur));
    flow += dfs(st, inf);
  }
  return flow;
}
}  // namespace dinic
namespace MFT {
int tim, vis[maxn];
int head[maxn];
struct edge {
  int to, nex, cost;
  edge(int to = 0, int nex = 0, int cost = 0) : to(to), nex(nex), cost(cost) {}
};
vector<edge> G;
inline void adde(int u, int v, int w) {
  an += w;
  G.push_back(edge(v, head[u], w)), head[u] = G.size() - 1;
  G.push_back(edge(u, head[v], w)), head[v] = G.size() - 1;
}
void dfs(int u, int c) {
  if (vis[u] == c) return;
  vis[u] = c;
  for (unsigned int i = 0; i < adj[u].size(); ++i) {
    node &e = adj[u][i];
    if (e.cap == e.flow) continue;
    dfs(e.to, c);
  }
}
void build(const vector<int> &V) {
  int n = V.size();
  if (n == 1) return;
  st = V[0], ed = V[1];
  edge_init(), adde(st, ed, dinic::maxflow());
  dfs(st, ++tim);
  vector<int> A, B;
  for (int i = 0; i < n; ++i) {
    if (vis[V[i]] == tim)
      A.push_back(V[i]);
    else
      B.push_back(V[i]);
  }
  build(A), build(B);
}
void init() {
  memset(head, -1, sizeof(head));
  vector<int> V;
  for (int i = 1; i <= n; ++i) V.push_back(i);
  build(V);
}
int FindMinEdge(int u, int fa) {
  int re = -1;
  for (int i = head[u]; ~i; i = G[i].nex) {
    int v = G[i].to;
    if (v == fa || vis[v] != tim) continue;
    int w = G[i].cost;
    if (re == -1 || w < G[re].cost) re = i;
    int t = FindMinEdge(v, u);
    if (t == -1) continue;
    if (G[t].cost < G[re].cost) re = t;
  }
  return re;
}
void travel(int u, int fa, vector<int> &V) {
  V.push_back(u);
  for (int i = head[u]; ~i; i = G[i].nex) {
    int v = G[i].to;
    if (v == fa || vis[v] != tim) continue;
    travel(v, u, V);
  }
}
void divide(const vector<int> &V) {
  int n = V.size();
  if (n == 1) {
    P.push_back(V[0]);
    return;
  }
  ++tim;
  for (int i = 0; i < n; ++i) {
    vis[V[i]] = tim;
  }
  int r = FindMinEdge(V[0], -1);
  int u = G[r].to, v = G[r ^ 1].to;
  vector<int> A, B;
  travel(u, v, A);
  travel(v, u, B);
  divide(A);
  divide(B);
}
void sol() {
  vector<int> V;
  for (int i = 1; i <= n; ++i) V.push_back(i);
  divide(V);
}
}  // namespace MFT
int main() {
  read(n), read(m);
  for (int i = 1; i <= m; ++i) {
    int a, b, c;
    read(a), read(b), read(c);
    addedge(a, b, c);
  }
  MFT::init();
  printf("%d\n", an);
  MFT::sol();
  for (int i = 0; i < n; ++i) {
    if (i) printf(" ");
    printf("%d", P[i]);
  }
  printf("\n");
  return 0;
}
