#include <bits/stdc++.h>
using namespace std;
template <int SZ>
struct Dinic {
  typedef long long F;
  struct Edge {
    int to, rev;
    F flow, cap;
  };
  int N, s, t;
  vector<Edge> adj[SZ];
  typename vector<Edge>::iterator cur[SZ];
  void addEdge(int u, int v, F cap) {
    assert(cap >= 0);
    Edge a{v, (int)adj[v].size(), 0, cap}, b{u, (int)adj[u].size(), 0, 0};
    adj[u].push_back(a), adj[v].push_back(b);
  }
  int level[SZ];
  bool bfs() {
    for (int i = 0; i <= N; i++) level[i] = -1, cur[i] = begin(adj[i]);
    queue<int> q({s});
    level[s] = 0;
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (auto &e : adj[u])
        if (level[e.to] < 0 && e.flow < e.cap)
          q.push(e.to), level[e.to] = level[u] + 1;
    }
    return level[t] >= 0;
  }
  F sendFlow(int v, F flow) {
    if (v == t) return flow;
    for (; cur[v] != end(adj[v]); cur[v]++) {
      Edge &e = *cur[v];
      if (level[e.to] != level[v] + 1 || e.flow == e.cap) continue;
      auto df = sendFlow(e.to, min(flow, e.cap - e.flow));
      if (df) {
        e.flow += df;
        adj[e.to][e.rev].flow -= df;
        return df;
      }
    }
    return 0;
  }
  F maxFlow(int n, int _s, int _t) {
    N = n, s = _s, t = _t;
    if (s == t) return -1;
    F tot = 0;
    while (bfs())
      while (auto df = sendFlow(s, numeric_limits<F>::max())) tot += df;
    return tot;
  }
};
template <int SZ>
struct GomoryHu {
  int N;
  vector<pair<pair<int, int>, int>> ed;
  void addEdge(int a, int b, int c) { ed.push_back({{a, b}, c}); }
  vector<vector<int>> cor = {{}};
  map<int, int> adj[2 * SZ];
  int side[SZ];
  int gen(vector<vector<int>> cc) {
    Dinic<SZ> D = Dinic<SZ>();
    vector<int> comp(N + 1);
    for (int i = 0; i < cc.size(); i++)
      for (auto &t : cc[i]) comp[t] = i;
    for (auto &t : ed)
      if (comp[t.first.first] != comp[t.first.second]) {
        D.addEdge(comp[t.first.first], comp[t.first.second], t.second);
        D.addEdge(comp[t.first.second], comp[t.first.first], t.second);
      }
    assert(cc.size() <= N);
    int f = D.maxFlow(N, 0, 1);
    for (int i = 0; i < cc.size(); i++)
      for (auto &j : cc[i]) side[j] = D.level[i] >= 0;
    return f;
  }
  void fill(vector<int> &v, int a, int b) {
    for (auto &t : cor[a]) v.push_back(t);
    for (auto &t : adj[a])
      if (t.first != b) fill(v, t.first, a);
  }
  void addTree(int a, int b, int c) { adj[a][b] = c, adj[b][a] = c; }
  void delTree(int a, int b) { adj[a].erase(b), adj[b].erase(a); }
  vector<pair<pair<int, int>, int>> init(int n) {
    N = n;
    for (int i = 1; i <= N; i++) cor[0].push_back(i);
    queue<int> todo;
    todo.push(0);
    while (!todo.empty()) {
      int x = todo.front();
      todo.pop();
      vector<vector<int>> cc;
      for (auto &t : cor[x]) cc.push_back({t});
      for (auto &t : adj[x]) {
        cc.push_back({});
        fill(cc.back(), t.first, x);
      }
      int f = gen(cc);
      cor.push_back({}), cor.push_back({});
      for (auto &t : cor[x]) cor[cor.size() - 2 + side[t]].push_back(t);
      for (int i = 0; i < 2; i++)
        if (cor[cor.size() - 2 + i].size() > 1) todo.push(cor.size() - 2 + i);
      for (int i = 0; i < cor.size() - 2; i++)
        if (i != x && adj[i].count(x)) {
          addTree(i, cor.size() - 2 + side[cor[i][0]], adj[i][x]);
          delTree(i, x);
        }
      addTree(cor.size() - 2, cor.size() - 1, f);
    }
    vector<pair<pair<int, int>, int>> ans;
    for (int i = 0; i < cor.size(); i++)
      for (auto &j : adj[i])
        if (i < j.first)
          ans.push_back({{cor[i][0], cor[j.first][0]}, j.second});
    return ans;
  }
  void dfs(int root, int node, int parent, int minimum,
           vector<vector<pair<int, int>>> &edges, vector<vector<int>> &f) {
    f[root][node] = minimum;
    for (pair<int, int> edge : edges[node])
      if (edge.first != parent)
        dfs(root, edge.first, node, min(minimum, edge.second), edges, f);
  }
  vector<vector<int>> allPairs(int n) {
    auto tree = init(n);
    vector<vector<int>> ret(n + 1, vector<int>(n + 1, 0));
    vector<vector<pair<int, int>>> edges(n + 1);
    for (auto e : tree) {
      edges[e.first.first].emplace_back(e.first.second, e.second);
      edges[e.first.second].emplace_back(e.first.first, e.second);
    }
    for (int i = 1; i <= n; i++) dfs(i, i, i, INT_MAX, edges, ret);
    return ret;
  }
};
int n, m, ans, maxi = -1, ma, mb, parent[220];
vector<int> order;
vector<pair<int, int>> adj[220];
int main() {
  GomoryHu<220> gh;
  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    int a, b, c;
    scanf("%d %d %d", &a, &b, &c);
    gh.addEdge(a, b, c);
  }
  auto tree = gh.init(n);
  for (auto ed : tree) {
    int a = ed.first.first, b = ed.first.second, c = ed.second;
    ans += c;
    if (maxi < c) {
      maxi = c;
      tie(ma, mb) = ed.first;
    }
    adj[a].emplace_back(c, b);
    adj[b].emplace_back(c, a);
  }
  order.push_back(ma);
  order.push_back(mb);
  priority_queue<pair<int, int>> thankyounext;
  for (auto ed : adj[ma])
    if (ed.second != mb) thankyounext.push(ed), parent[ed.second] = ma;
  for (auto ed : adj[mb])
    if (ed.second != ma) thankyounext.push(ed), parent[ed.second] = mb;
  while (!thankyounext.empty()) {
    int u = thankyounext.top().second;
    thankyounext.pop();
    order.push_back(u);
    for (auto ed : adj[u])
      if (ed.second != parent[u]) thankyounext.push(ed), parent[ed.second] = u;
  }
  printf("%d\n", ans);
  for (int x : order) printf("%d ", x);
  return 0;
}
