#include <bits/stdc++.h>
using namespace std;
const int inft = 1000000009;
const int MAXN = 206;
typedef int type;
const type inf = 1 << 28;
vector<int> V[MAXN];
int n, ujscie, zrodlo;
type M[MAXN][MAXN];
int pocz[MAXN], w[MAXN], Q[MAXN];
type dfs(int u, type ile) {
  if (u == ujscie || ile == 0) return ile;
  type t, ans = 0;
  for (int k = pocz[u]; k < V[u].size(); ++k, ++pocz[u])
    if (w[V[u][k]] == w[u] + 1 && M[u][V[u][k]] > 0) {
      t = dfs(V[u][k], min(M[u][V[u][k]], ile));
      M[u][V[u][k]] -= t;
      M[V[u][k]][u] += t;
      ile -= t;
      ans += t;
      if (ile == 0) break;
    }
  return ans;
}
bool bfs() {
  for (int i = 0; i < (n); ++i) w[i] = -1;
  int ct = 0;
  Q[ct++] = zrodlo;
  w[zrodlo] = 1;
  for (int i = 0; i < (ct); ++i)
    for (typeof((V[Q[i]]).begin()) it = (V[Q[i]]).begin();
         it != (V[Q[i]]).end(); ++it)
      if (w[*it] == -1 && M[Q[i]][*it] > 0) {
        Q[ct++] = *it;
        w[*it] = w[Q[i]] + 1;
      }
  return w[ujscie] != -1;
}
vector<pair<int, int> > JAK;
type maxflow() {
  type ans = 0;
  while (bfs()) {
    for (int i = 0; i < (n); ++i) pocz[i] = 0;
    ans += dfs(zrodlo, inf);
  }
  JAK.clear();
  for (int i = 0; i < (n); ++i)
    for (typeof((V[i]).begin()) it = (V[i]).begin(); it != (V[i]).end(); ++it)
      if (w[i] != -1 && w[*it] == -1) JAK.push_back(pair<int, int>(i, *it));
  return ans;
}
void addedge(int a, int b, type k) {
  if (a == b) return;
  M[a][b] += k;
  V[a].push_back(b);
  V[b].push_back(a);
}
vector<pair<int, type> > GH[MAXN];
int gh[MAXN];
int M2[MAXN][MAXN];
void BuildGH(int l, int r) {
  if (l == r) return;
  for (int a = 0; a < (n); ++a)
    for (int b = 0; b < (n); ++b) M[a][b] = M2[a][b];
  zrodlo = gh[l];
  ujscie = gh[r];
  int flow = maxflow(), i, j;
  for (i = l + 1, j = l; i <= r; ++i)
    if (w[gh[i]] != -1) swap(gh[++j], gh[i]);
  GH[gh[l]].push_back(make_pair(gh[r], flow));
  GH[gh[r]].push_back(make_pair(gh[l], flow));
  ;
  BuildGH(l, j);
  BuildGH(j + 1, r);
}
type GomoryHu() {
  for (int i = 0; i < (n); ++i)
    for (int j = 0; j < (n); ++j) M2[i][j] = M[i][j];
  for (int i = 0; i < (n); ++i) gh[i] = i;
  BuildGH(0, n - 1);
  type ret = 0;
  for (int i = 0; i < (n); ++i)
    for (typeof((GH[i]).begin()) it = (GH[i]).begin(); it != (GH[i]).end();
         ++it)
      ret += it->second;
  return ret / 2;
}
int bestval, bp, bk;
vector<int> ans;
void dfs2(int u, int par) {
  for (typeof((GH[u]).begin()) it = (GH[u]).begin(); it != (GH[u]).end(); ++it)
    if (it->first != par) {
      dfs2(it->first, u);
      if (bestval == -1 || it->second < bestval) {
        bestval = it->second;
        bp = u;
        bk = it->first;
      }
    }
}
void usun(vector<pair<int, int> > &a, int b) {
  for (int i = 0; i < (a.size()); ++i)
    if (a[i].first == b) {
      swap(a[i], a.back());
      a.pop_back();
      return;
    }
}
void wynik(int u) {
  bestval = bp = bk = -1;
  ;
  dfs2(u, -1);
  if (bestval == -1) {
    ans.push_back(u);
    return;
  };
  usun(GH[bp], bk);
  usun(GH[bk], bp);
  int bk2 = bk;
  wynik(bp);
  wynik(bk2);
}
int main() {
  int m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < (m); ++i) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    --a;
    --b;
    addedge(a, b, c);
    addedge(b, a, c);
  }
  for (int i = 0; i < (n); ++i) sort((V[i]).begin(), (V[i]).end());
  for (int i = 0; i < (n); ++i)
    V[i].resize(unique((V[i]).begin(), (V[i]).end()) - V[i].begin());
  printf("%d\n", GomoryHu());
  wynik(0);
  for (typeof((ans).begin()) it = (ans).begin(); it != (ans).end(); ++it)
    printf("%d ", *it + 1);
  puts("");
  return 0;
}
