#include <bits/stdc++.h>
using namespace std;
const int N = 500 + 5, inf = 0x3f3f3f3f;
namespace network_flow {
struct edge {
  int to, nxt, val, cost;
} e[N << 5];
int head[N], cnt = 1, maxflow, vis[N], dis[N], nxt[N];
int s, t;
void add_edge(int x, int y, int z) {
  e[++cnt].to = y;
  e[cnt].val = z;
  e[cnt].nxt = head[x];
  head[x] = cnt;
}
void add(int x, int y, int z) {
  add_edge(x, y, z);
  add_edge(y, x, 0);
}
queue<int> q;
bool spfa() {
  memset(dis, 0x3f, sizeof(dis));
  dis[s] = 0;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = 0;
    for (int i = head[u]; i; i = e[i].nxt)
      if (e[i].val && dis[e[i].to] > dis[u] + 1) {
        dis[e[i].to] = dis[u] + 1;
        if (!vis[e[i].to]) vis[e[i].to] = 1, q.push(e[i].to);
      }
  }
  return (dis[t]) ^ inf;
}
bool flag[N];
int n;
int dfs(int u, int limit) {
  if (u == t) return limit;
  int flow = 0;
  for (int i = head[u]; i && limit; i = e[i].nxt)
    if (e[i].val && dis[e[i].to] == dis[u] + 1) {
      int k = dfs(e[i].to, min(limit, e[i].val));
      if (k > 0) {
        e[i].val -= k;
        e[i ^ 1].val += k;
        limit -= k;
        flow += k;
      }
    }
  if (!flow) dis[u] = inf;
  return flow;
}
void Dinic() {
  for (int i = 2; i <= cnt; ++i) e[i].val += e[i ^ 1].val, e[i ^ 1].val = 0;
  maxflow = 0;
  while (spfa()) maxflow += dfs(s, inf);
}
};  // namespace network_flow
int ans[N], ccnt, Ans;
namespace mincut_tree {
struct edge {
  int nxt, to, val, vis;
} e[N << 4];
int head[N], cnt = 1;
void add(int x, int y, int z) {
  e[++cnt].to = y;
  e[cnt].val = z;
  e[cnt].nxt = head[x];
  head[x] = cnt;
  e[++cnt].to = x;
  e[cnt].val = z;
  e[cnt].nxt = head[y];
  head[y] = cnt;
}
int x, y, mn, pos;
void dfs(int u, int fath) {
  for (int i = head[u]; i; i = e[i].nxt)
    if (e[i].to != fath && e[i].vis == 0) {
      if (mn > e[i].val) mn = e[i].val, pos = i, x = u, y = e[i].to;
      dfs(e[i].to, u);
    }
}
void solve(int u) {
  mn = inf;
  dfs(u, 0);
  if (mn == inf) return ans[++ccnt] = u, void(0);
  Ans += mn;
  e[pos].vis = e[pos ^ 1].vis = 1;
  int a = x, b = y;
  solve(a);
  solve(b);
}
}  // namespace mincut_tree
int node[N], tmp1[N], tmp2[N];
void build(int l, int r) {
  if (l == r) return;
  network_flow::s = node[l];
  network_flow::t = node[l + 1];
  network_flow::Dinic();
  int cnt1 = 0, cnt2 = 0;
  mincut_tree::add(network_flow::s, network_flow::t, network_flow::maxflow);
  for (int i = l; i <= r; ++i)
    if (network_flow::dis[node[i]] ^ inf)
      tmp1[++cnt1] = node[i];
    else
      tmp2[++cnt2] = node[i];
  for (int i = 1; i <= cnt1; ++i) node[l + i - 1] = tmp1[i];
  for (int i = 1; i <= cnt2; ++i) node[l + cnt1 + i - 1] = tmp2[i];
  build(l, l + cnt1 - 1);
  build(l + cnt1, r);
}
int main() {
  int u, v, n, m, val;
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    cin >> u >> v >> val;
    network_flow::add(u, v, val);
    network_flow::add(v, u, val);
  }
  for (int i = 1; i <= n; ++i) node[i] = i;
  build(1, n);
  mincut_tree::solve(1);
  cout << Ans << endl;
  for (int i = 1; i <= ccnt; ++i) cout << ans[i] << " ";
  return 0;
}
