#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:66777216")
using namespace std;
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;
    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;
          return rr;
        }
      }
    }
    return 0;
  }
  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;
  }
};
int a, b, c, d, n, m, k;
DinicFlow<int, 205, 2100> q;
int ds[202][202];
bool used[202];
int main() {
  scanf("%d%d", &n, &m);
  q.reset(n + 2);
  for (int _n((m)-1), i(0); i <= _n; i++) {
    scanf("%d%d%d", &a, &b, &c);
    --a;
    --b;
    q.addEdge(a, b, c, c);
  }
  for (int _n((n)-1), i(0); i <= _n; i++) {
    for (int _n((i)-1), j(0); j <= _n; j++) {
      memset((q.flow), 0, sizeof(q.flow));
      q.S = i;
      q.T = j;
      ds[i][j] = ds[j][i] = q.maxFlow();
    }
  }
  vector<int> ans;
  int mx = 0;
  for (int _n((n)-1), i(0); i <= _n; i++) {
    for (int _n((i)-1), j(0); j <= _n; j++) {
      if (ds[i][j] > mx) {
        ans.clear();
        ans.push_back(i);
        ans.push_back(j);
        mx = ds[i][j];
      }
    }
  }
  memset((used), 0, sizeof(used));
  used[ans[0]] = used[ans[1]] = 1;
  while ((int)((ans).size()) < n) {
    int mx = -1, v = -1;
    for (int _n((n)-1), i(0); i <= _n; i++) {
      if (used[i]) continue;
      if (ds[ans.back()][i] > mx) {
        mx = ds[ans.back()][i];
        v = i;
      }
    }
    ans.push_back(v);
    used[v] = 1;
  }
  int res = 0;
  for (int _n(((int)((ans).size()) - 1) - 1), i(0); i <= _n; i++)
    res += ds[ans[i]][ans[i + 1]];
  printf("%d\n", res);
  for (int _n(((int)((ans).size())) - 1), i(0); i <= _n; i++) {
    if (i) printf(" ");
    printf("%d", ans[i] + 1);
  }
  printf("\n");
}
