#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
class Edge {
 public:
  int from, to;
  Edge() {}
  Edge(int from, int to) : from(from), to(to) {}
};
class TreeEdge : public Edge {
 public:
  int w;
  TreeEdge(int from, int to, int w) : Edge(from, to), w(w) {}
};
class NetworkEdge : public Edge {
 public:
  int cap, flow, rev;
  NetworkEdge(int from, int to, int cap, int rev)
      : Edge(from, to), cap(cap), flow(0), rev(rev) {}
};
class Network {
 private:
  int n;
  vector<vector<NetworkEdge> > g;
  void clearEdgesFlow();

 public:
  explicit Network(int n) : n(n), g(vector<vector<NetworkEdge> >(n)) {}
  void addEdge(int from, int to, int cap);
  int minCut(int s, int t, vector<int>& vs, vector<int>& vt);
  vector<TreeEdge> getGomoriHuTree();
};
void Network::addEdge(int from, int to, int cap) {
  NetworkEdge dir(from, to, cap, (int)g[to].size());
  NetworkEdge rev(to, from, 0, (int)g[from].size());
  g[from].push_back(dir);
  g[to].push_back(rev);
}
void Network::clearEdgesFlow() {
  for (int v = 0; v < n; v++) {
    for (int i = 0; i < g[v].size(); i++) g[v][i].flow = 0;
  }
}
int Network::minCut(int s, int t, vector<int>& vs, vector<int>& vt) {
  clearEdgesFlow();
  vector<bool> used(n);
  vector<int> flow(n);
  vector<int> pv(n), pe(n);
  int curFlow = 0;
  while (true) {
    fill(used.begin(), used.end(), false);
    flow[s] = INF;
    used[s] = true;
    queue<int> q;
    q.push(s);
    while (!q.empty() && !used[t]) {
      int u = q.front();
      q.pop();
      for (int i = 0; i < g[u].size(); i++) {
        NetworkEdge& e = g[u][i];
        if (e.flow < e.cap && !used[e.to]) {
          used[e.to] = true;
          flow[e.to] = min(flow[u], e.cap - e.flow);
          pv[e.to] = u;
          pe[e.to] = i;
          q.push(e.to);
        }
      }
    }
    if (!used[t]) break;
    curFlow += flow[t];
    int v = t;
    while (v != s) {
      g[pv[v]][pe[v]].flow += flow[t];
      g[v][g[pv[v]][pe[v]].rev].flow -= flow[t];
      v = pv[v];
    }
  }
  vs.clear(), vt.clear();
  for (int v = 0; v < n; v++) {
    if (used[v])
      vs.push_back(v);
    else
      vt.push_back(v);
  }
  return curFlow;
}
vector<TreeEdge> Network::getGomoriHuTree() {
  vector<TreeEdge> e;
  vector<int> p(n, 0);
  for (int v = 1; v < n; v++) {
    vector<int> x, y;
    int cut = minCut(v, p[v], x, y);
    e.push_back(TreeEdge(v, p[v], cut));
    for (int i = 0; i < x.size(); i++) {
      int u = x[i];
      if (u > v && p[u] == p[v]) p[u] = v;
    }
  }
  return e;
}
const int MAXN = 205;
int d[MAXN][MAXN];
vector<TreeEdge> t[MAXN];
void go(int s, int v, int p, int minW) {
  d[s][v] = minW;
  for (int i = 0; i < t[v].size(); i++) {
    int u = t[v][i].to;
    if (u != p) go(s, u, v, min(minW, t[v][i].w));
  }
}
int main() {
  int n, m;
  cin >> n >> m;
  Network network(n);
  for (int i = 0; i < m; i++) {
    int x, y, w;
    cin >> x >> y >> w;
    x--, y--;
    network.addEdge(x, y, w);
    network.addEdge(y, x, w);
  }
  vector<TreeEdge> e = network.getGomoriHuTree();
  for (int i = 0; i < e.size(); i++) {
    t[e[i].from].push_back(e[i]);
    swap(e[i].from, e[i].to);
    t[e[i].from].push_back(e[i]);
  }
  for (int i = 0; i < n; i++) go(i, i, -1, INF);
  vector<int> p;
  p.push_back(0);
  vector<bool> used(n, false);
  used[0] = true;
  for (int i = 0; i < n - 1; i++) {
    int v = p[i], best = -1;
    for (int u = 0; u < n; u++) {
      if (!used[u] && (best == -1 || d[v][u] > d[v][best])) best = u;
    }
    used[best] = true;
    p.push_back(best);
  }
  int ans = 0;
  for (int i = 0; i < n - 1; i++) ans += d[p[i]][p[i + 1]];
  cout << ans << endl;
  for (int i = 0; i < n; i++) cout << p[i] + 1 << " ";
  cout << endl;
  return 0;
}
