#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline bool chkmin(T &a, const T &b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T>
inline bool chkmax(T &a, const T &b) {
  return a < b ? a = b, 1 : 0;
}
const int oo = 0x3f3f3f3f;
const int maxn = 200;
const int max0 = 200, max1 = 4000;
struct edge {
  int id, g, nxt;
  edge() {}
  edge(int _id, int _g, int _nxt) : id(_id), g(_g), nxt(_nxt) {}
};
int st[max0 + 5], en = 0;
edge e[max1 + 5];
inline void add_edge(int first, int second, int z) {
  e[en] = edge(second, z, st[first]), st[first] = en++;
}
int n, m;
int S, T, N;
int dis[max0 + 5];
inline bool bfs() {
  static int q[max0 + 5];
  static bool vis[max0 + 5];
  int head = 0, rear = 0;
  memset(dis, -1, sizeof(dis[0]) * N);
  memset(vis, 0, sizeof(vis[0]) * N);
  vis[q[rear++] = S] = 1;
  dis[S] = 0;
  while (head != rear) {
    int first = q[head++];
    for (int i = st[first]; i != -1; i = e[i].nxt) {
      if (!e[i].g) continue;
      int second = e[i].id;
      if (!vis[second]) {
        dis[second] = dis[first] + 1;
        if (second == T) return 1;
        q[rear++] = second;
        vis[second] = 1;
      }
    }
  }
  return 0;
}
inline int dfs(int first, int flow) {
  if (first == T) return flow;
  int res = flow;
  for (int i = st[first]; i != -1; i = e[i].nxt) {
    if (!e[i].g) continue;
    int second = e[i].id;
    if (dis[second] == dis[first] + 1) {
      int F = dfs(second, min(e[i].g, res));
      res -= F;
      e[i].g -= F;
      e[i ^ 1].g += F;
      if (res <= 0) return flow;
    }
  }
  dis[first] = -1;
  return flow - res;
}
int work() {
  if (S == T) return oo;
  int ret = 0;
  for (; bfs(); ret += dfs(S, oo))
    ;
  return ret;
}
int f[maxn + 5][maxn + 5], g[maxn + 5][maxn + 5];
int ans;
void work(vector<int> &all) {
  if ((int((all).size())) == 1) return;
  for (int i = (0), _end_ = (en >> 1); i < _end_; ++i) {
    int a = e[i << 1].g, b = e[i << 1 | 1].g;
    e[i << 1].g = (a + b) >> 1, e[i << 1 | 1].g = (a + b) >> 1;
  }
  S = all[0], T = all[1];
  int tmp = work();
  ans += tmp;
  chkmin(f[S][T], tmp);
  chkmin(f[T][S], tmp);
  chkmin(g[S][T], tmp);
  chkmin(g[T][S], tmp);
  static bool vis[maxn + 5];
  memset(vis, 0, sizeof(vis[0]) * N);
  static int q[maxn + 5];
  int head = 0, rear = 0;
  q[rear++] = S;
  vis[S] = 1;
  while (head != rear) {
    int first = q[head++];
    for (int i = st[first]; i != -1; i = e[i].nxt) {
      if (!e[i].g) continue;
      int second = e[i].id;
      if (!vis[second]) q[rear++] = second, vis[second] = 1;
    }
  }
  vector<int> a, b;
  for (auto first : all)
    if (vis[first])
      a.push_back(first);
    else
      b.push_back(first);
  all.clear();
  work(a), work(b);
}
int main() {
  memset(st, -1, sizeof st), en = 0;
  memset(f, oo, sizeof f);
  memset(g, oo, sizeof g);
  scanf("%d%d", &n, &m);
  for (int i = (0), _end_ = (n); i < _end_; ++i) g[i][i] = 0;
  N = n;
  for (int i = (0), _end_ = (m); i < _end_; ++i) {
    int first, second, z;
    scanf("%d%d%d", &first, &second, &z), --first, --second;
    add_edge(first, second, z);
    add_edge(second, first, z);
  }
  vector<int> all;
  for (int i = (0), _end_ = (n); i < _end_; ++i) all.push_back(i);
  work(all);
  for (int k = (0), _end_ = (n); k < _end_; ++k)
    for (int i = (0), _end_ = (n); i < _end_; ++i)
      for (int j = (0), _end_ = (n); j < _end_; ++j)
        chkmin(g[i][j], g[i][k] + g[k][j]);
  for (int i = (0), _end_ = (n); i < _end_; ++i)
    for (int j = (0), _end_ = (n); j < _end_; ++j)
      for (int k = (0), _end_ = (n); k < _end_; ++k)
        if (g[i][k] == g[i][j] + g[j][k])
          chkmin(f[i][k], min(f[i][j], f[j][k]));
  printf("%d\n", ans);
  int cur = 0;
  static bool vis[maxn + 5];
  memset(vis, 0, sizeof vis);
  int ans0 = 0;
  for (int i = (0), _end_ = (n); i < _end_; ++i) {
    vis[cur] = 1;
    printf("%d ", cur + 1);
    if (i + 1 < n) {
      int Maxp = -1;
      for (int j = (0), _end_ = (n); j < _end_; ++j)
        if (!vis[j] && (Maxp == -1 || f[cur][j] > f[cur][Maxp])) Maxp = j;
      ans0 += f[cur][Maxp];
      cur = Maxp;
    }
  }
  assert(ans == ans0);
  return 0;
}
