#include <bits/stdc++.h>
#pragma GCC optimize "-O3"
using namespace std;
const int N = 301;
const int inf = 0x3f3f3f3f;
struct Dinitz {
  int n, S, T, d[N];
  struct Edge {
    int u, v, c;
    Edge(int u, int v, int c) : u(u), v(v), c(c) {}
  };
  vector<int> g[N];
  vector<Edge> E;
  void addEdge(int u, int v, int c) {
    g[u].push_back(E.size());
    E.push_back({u, v, c});
    g[v].push_back(E.size());
    E.push_back({v, u, c});
  }
  bool bfs() {
    for (int i = 1; i <= n; ++i) d[i] = 0;
    queue<int> q;
    d[S] = 1;
    q.push(S);
    while (q.size()) {
      int u = q.front();
      q.pop();
      if (u == T) return 1;
      for (int i : g[u]) {
        if (!E[i].c || d[E[i].v]) continue;
        d[E[i].v] = d[u] + 1;
        q.push(E[i].v);
      }
    }
    return 0;
  }
  int dfs(int u, int Min) {
    if (u == T || !Min) return Min;
    for (int i : g[u]) {
      int v = E[i].v;
      if (!E[i].c || d[v] != d[u] + 1) continue;
      int res = dfs(v, min(Min, E[i].c));
      if (res) {
        E[i].c -= res;
        E[i ^ 1].c += res;
        return res;
      }
    }
    return 0;
  }
  int calc(int s, int t) {
    S = s, T = t;
    int ans = 0;
    while (bfs())
      while (int cur = dfs(S, inf)) ans += cur;
    return ans;
  }
} C;
int p[N], n, m;
bool vis[N];
int g[N][N];
void remark(int u) {
  vis[u] = 1;
  for (int i : C.g[u]) {
    Dinitz::Edge &e = C.E[i];
    if (e.c && !vis[e.v]) remark(e.v);
  }
}
void solve() {
  int ans = 0;
  for (int i = 1; i <= n; ++i) p[i] = 1;
  for (int i = 2; i <= n; ++i) {
    for (int j = 0; j < C.E.size(); j += 2)
      C.E[j].c = C.E[j ^ 1].c = (C.E[j].c + C.E[j ^ 1].c) >> 1;
    int cur = C.calc(i, p[i]);
    memset(vis, 0, sizeof vis);
    remark(i);
    for (int j = i + 1; j <= n; ++j)
      if (vis[j] && p[j] == p[i]) p[j] = i;
    g[p[i]][i] = cur;
    ans += cur;
  }
  cout << ans << "\n1";
  memset(vis, 0, sizeof vis);
  vis[1] = 1;
  priority_queue<pair<int, int> > q;
  for (int i = 1; i <= n; ++i)
    if (g[1][i]) q.push({g[1][i], i}), vis[i] = 1;
  while (q.size()) {
    int u = q.top().second;
    q.pop();
    cout << " " << u;
    for (int i = 1; i <= n; ++i)
      if (!vis[i] && g[u][i]) q.push({g[u][i], i}), vis[i] = 1;
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  C.n = n;
  while (m--) {
    int u, v, c;
    cin >> u >> v >> c;
    C.addEdge(u, v, c);
  }
  solve();
}
