#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1073741824")
using namespace std;
const int nmax = 210;
int c[nmax][nmax];
int f[nmax][nmax];
vector<int> g[nmax];
int G[nmax][nmax];
vector<int> Gv[nmax];
bool used[nmax];
int T;
int d[nmax];
int q[nmax];
queue<int> gv[nmax];
bool bfs(int s, int t) {
  memset((d), -1, sizeof(d));
  d[s] = 0;
  int ql = 0;
  int qr = 0;
  q[qr++] = s;
  while (ql < qr) {
    int v = q[ql++];
    for (int(i) = 0; (i) < (int((g[v]).size())); ++(i)) {
      int to = g[v][i];
      if (d[to] == -1 && f[v][to] < c[v][to]) {
        d[to] = d[v] + 1;
        q[qr++] = to;
      }
    }
  }
  return d[t] != -1;
}
int idx[nmax];
bool dfs(int v, int mn) {
  if (v == T) return mn;
  used[v] = true;
  for (; idx[v] < g[v].size(); ++idx[v]) {
    int to = g[v][idx[v]];
    if (!used[to] && d[to] == d[v] + 1 && f[v][to] < c[v][to]) {
      int val = dfs(to, min(mn, c[v][to] - f[v][to]));
      if (val) {
        f[v][to] += val;
        f[to][v] -= val;
        return val;
      }
    }
  }
  return 0;
}
int flow(int s, int t) {
  memset((f), 0, sizeof(f));
  T = t;
  int res = 0;
  while (bfs(s, t)) {
    memset((idx), 0, sizeof(idx));
    memset((used), 0, sizeof(used));
    int val;
    while (val = dfs(s, 1000000000)) {
      res += val;
    }
  }
  return res;
}
void dfsReachable(int v) {
  used[v] = true;
  for (int(i) = 0; (i) < (int((g[v]).size())); ++(i)) {
    int to = g[v][i];
    if (!used[to] && f[v][to] < c[v][to]) dfsReachable(to);
  }
}
int comp[nmax];
void dfsFindBest(int v) {
  used[v] = true;
  for (int(i) = 0; (i) < (int((Gv[v]).size())); ++(i)) {
    int to = Gv[v][i];
    if (!used[to] && G[v][to]) dfsFindBest(to);
  }
}
vector<int> findBest(vector<int> a) {
  if (a.size() == 1) return a;
  int curMin = 1000000000;
  int v = -1, u = -1;
  for (int(i) = 0; (i) < (int((a).size())); ++(i))
    for (int(j) = 0; (j) < (int((a).size())); ++(j))
      if (G[a[i]][a[j]] && curMin > G[a[i]][a[j]]) {
        curMin = G[a[i]][a[j]];
        v = a[i];
        u = a[j];
      }
  G[v][u] = G[u][v] = 0;
  memset((used), 0, sizeof(used));
  dfsFindBest(v);
  vector<int> b;
  vector<int> c;
  for (int(i) = 0; (i) < (int((a).size())); ++(i)) {
    if (used[a[i]]) {
      b.push_back(a[i]);
    } else {
      c.push_back(a[i]);
    }
  }
  vector<int> B = findBest(b);
  vector<int> C = findBest(c);
  for (int(i) = 0; (i) < (int((C).size())); ++(i)) B.push_back(C[i]);
  return B;
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int(i) = 0; (i) < (m); ++(i)) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    --x;
    --y;
    c[x][y] = c[y][x] = z;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  int ans = 0;
  for (int(k) = 0; (k) < (n - 1); ++(k)) {
    int s = -1, t = -1;
    for (int(i) = 0; (i) < (n); ++(i)) {
      for (int(j) = 0; (j) < (n); ++(j)) {
        if (i != j && comp[i] == comp[j]) {
          s = i;
          t = j;
        }
      }
    }
    assert(s != -1 && t != -1 && s != t);
    int flowFound = flow(s, t);
    ans += flowFound;
    G[s][t] = G[t][s] = flowFound;
    Gv[s].push_back(t);
    Gv[t].push_back(s);
    memset((used), 0, sizeof(used));
    dfsReachable(s);
    for (int(i) = 0; (i) < (n); ++(i))
      if (comp[i] == comp[s] && !used[i]) comp[i] = k + 1;
  }
  cout << ans << endl;
  vector<int> a(n);
  for (int(i) = 0; (i) < (n); ++(i)) a[i] = i;
  a = findBest(a);
  for (int(i) = 0; (i) < (n); ++(i))
    cout << a[i] + 1 << (i + 1 == n ? "\n" : " ");
  return 0;
}
