#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:1073741824")
using namespace std;
const int nmax = 210;
const int kmax = 2 * 1010;
struct edge {
  short to;
  short rem;
  int next;
  edge() {
    to = rem = -1;
    next = -1;
  }
  edge(int to_, int c_) {
    to = to_;
    rem = c_;
    next = -1;
  }
} edges[kmax];
int initRem[kmax];
int gFirst[nmax];
bool used[nmax];
int T;
int d[nmax];
int q[nmax];
int M;
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 cur = gFirst[v]; cur != -1; cur = edges[cur].next) {
      int to = edges[cur].to;
      if (d[to] == -1 && edges[cur].rem) {
        d[to] = d[v] + 1;
        q[qr++] = to;
      }
    }
  }
  return d[t] != -1;
}
int idx[nmax];
int dfs(int v, int mn) {
  if (v == T) return mn;
  used[v] = true;
  int pushed = 0;
  for (; idx[v] != -1; idx[v] = edges[idx[v]].next) {
    int to = edges[idx[v]].to;
    short& rem = edges[idx[v]].rem;
    short& revRem = edges[idx[v] ^ 1].rem;
    if (!used[to] && d[to] == d[v] + 1 && rem) {
      int val = dfs(to, min(mn - pushed, (int)rem));
      if (val) {
        rem -= val;
        revRem += val;
        pushed += val;
      }
    }
    if (pushed == mn) break;
  }
  return pushed;
}
int N;
int flow(int s, int t) {
  for (int(i) = 0; (i) < (2 * M); ++(i)) edges[i].rem = initRem[i >> 1];
  T = t;
  int res = 0;
  while (bfs(s, t)) {
    for (int(v) = 0; (v) < (N); ++(v)) idx[v] = gFirst[v];
    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 cur = gFirst[v]; cur != -1; cur = edges[cur].next) {
    int to = edges[cur].to;
    int rem = edges[cur].rem;
    if (!used[to] && rem) dfsReachable(to);
  }
}
int comp[nmax];
int G[nmax][nmax];
vector<int> Gv[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);
  }
}
inline bool isUsed(int v) { return used[v]; }
void findBest(int* a, int* c, int answer[]) {
  if (a + 1 == c) {
    answer[0] = a[0];
    return;
  }
  int curMin = 1000000000;
  int v = -1, u = -1;
  for (int(i) = 0; (i) < (c - a); ++(i))
    for (int(j) = 0; (j) < (i); ++(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);
  int* b = partition(a, c, isUsed);
  findBest(a, b, answer);
  findBest(b, c, answer + (b - a));
}
int gLast[nmax];
int main() {
  memset((gLast), -1, sizeof(gLast));
  int n, m;
  scanf("%d%d", &n, &m);
  N = n;
  M = m;
  for (int(i) = 0; (i) < (m); ++(i)) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    --x;
    --y;
    if (gLast[x] != -1) {
      edges[gLast[x]].next = 2 * i;
    } else {
      gFirst[x] = 2 * i;
    }
    if (gLast[y] != -1) {
      edges[gLast[y]].next = 2 * i + 1;
    } else {
      gFirst[y] = 2 * i + 1;
    }
    gLast[x] = 2 * i;
    gLast[y] = 2 * i + 1;
    edges[gLast[x]] = edge(y, z);
    edges[gLast[y]] = edge(x, z);
    initRem[i] = z;
  }
  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;
  int a[nmax];
  int answer[nmax];
  for (int(i) = 0; (i) < (n); ++(i)) a[i] = i;
  findBest(a, a + n, answer);
  for (int(i) = 0; (i) < (n); ++(i))
    cout << answer[i] + 1 << (i + 1 == n ? "\n" : " ");
  return 0;
}
