#include <bits/stdc++.h>
using namespace std;
long long rdtsc() {
  long long tmp;
  asm("rdtsc" : "=A"(tmp));
  return tmp;
}
inline int myrand() { return abs((rand() << 15) ^ rand()); }
inline int rnd(int x) { return myrand() % x; }
const int INF = (int)1e9 + 1;
const long double EPS = 1e-9;
template <typename TT, int V, int E>
struct DinicFlow {
  int ds[V + 1], q[V + 1], nx[E + 1], last[V + 1], ver[E + 1], now[V + 1], n,
      edgesCount, S, T;
  TT cap[E + 1], flow[E + 1];
  DinicFlow() : n(0), S(0), T(0), edgesCount(0) {}
  DinicFlow(int _n) : n(_n), S(0), T(0), edgesCount(0) {}
  inline void reset(int _n) {
    edgesCount = 0;
    n = _n;
    memset(last, -1, n * sizeof(int));
  }
  inline void addEdge(int v, int w, TT c, TT rc) {
    ver[edgesCount] = w;
    cap[edgesCount] = c;
    flow[edgesCount] = 0;
    nx[edgesCount] = last[v];
    last[v] = edgesCount++;
    ver[edgesCount] = v;
    cap[edgesCount] = rc;
    flow[edgesCount] = 0;
    nx[edgesCount] = last[w];
    last[w] = edgesCount++;
  }
  inline bool bfs() {
    memset(ds, 63, n * sizeof(int));
    int a = 0, b = 0;
    ds[T] = 0;
    q[0] = T;
    while (a <= b) {
      int v = q[a++];
      for (int w = last[v]; w >= 0; w = nx[w]) {
        if (cap[w ^ 1] - flow[w ^ 1] && ds[ver[w]] > ds[v] + 1) {
          ds[ver[w]] = ds[v] + 1;
          q[++b] = ver[w];
        }
      }
    }
    return ds[S] < 1000000000;
  }
  TT dfs(int v, TT cur) {
    if (v == T) return cur;
    int ans = 0;
    for (int &w = now[v]; w >= 0; w = nx[w]) {
      if (cap[w] - flow[w] && ds[ver[w]] == ds[v] - 1) {
        TT rr = dfs(ver[w], min(cur, cap[w] - flow[w]));
        if (rr) {
          flow[w] += rr;
          flow[w ^ 1] -= rr;
          ans += rr;
          cur -= rr;
          if (!cur) break;
        }
      }
    }
    return ans;
  }
  inline TT maxFlow() {
    TT ans = 0;
    while (bfs()) {
      memcpy(now, last, n * sizeof(int));
      TT tf;
      while (tf = dfs(S, 1000000000)) ans += tf;
    }
    return ans;
  }
};
const int maxn = 200 + 10;
int dist[maxn][maxn];
int used[maxn];
DinicFlow<int, 205, 2100> F;
bool solve() {
  int n, m;
  if (scanf("%d%d", &n, &m) < 2) {
    return 0;
  }
  F.reset(n + 2);
  for (int i = 0; i < m; ++i) {
    int s, t, c;
    scanf("%d%d%d", &s, &t, &c);
    --s, --t;
    F.addEdge(s, t, c, c);
  }
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      memset(F.flow, 0, sizeof(F.flow));
      F.S = i, F.T = j;
      dist[j][i] = dist[i][j] = F.maxFlow();
    }
  }
  for (int i = 0; i < n; ++i) {
    used[i] = 0;
  }
  vector<int> ans;
  int res = 0;
  for (int v = 0, iter = 0; iter < n; ++iter) {
    ans.push_back(v);
    used[v] = 1;
    if (iter == n - 1) {
      break;
    }
    int best = -1, bestv = -1;
    int *cur = dist[v];
    for (int u = 0; u < n; ++u) {
      if (!used[u] && best < cur[u]) {
        best = cur[u];
        bestv = u;
      }
    }
    assert(bestv != -1);
    res += best;
    v = bestv;
  }
  printf("%d\n", res);
  for (int i = 0; i < ((int)(ans).size()); ++i) {
    printf("%d ", ans[i] + 1);
  }
  printf("\n");
  return 1;
}
int main() {
  srand(rdtsc());
  while (1) {
    if (!solve()) {
      break;
    }
  }
  return 0;
}
