#include <bits/stdc++.h>
using namespace std;
const int max_n = 205, inf = 1e9 + 100;
struct Dinic {
  struct edge {
    int to, cap, flow;
  };
  vector<int> v[max_n];
  vector<edge> ed;
  int d[max_n];
  int st[max_n];
  void AddEdge(int from, int to, int cap, int flow = 0) {
    v[from].push_back(ed.size());
    ed.push_back(edge{to, cap, flow});
    v[to].push_back(ed.size());
    ed.push_back(edge{from, 0, -flow});
  }
  void AddEdgeIndir(int from, int to, int cap, int flow = 0) {
    v[from].push_back(ed.size());
    ed.push_back(edge{to, cap, flow});
    v[to].push_back(ed.size());
    ed.push_back(edge{from, cap, -flow});
  }
  bool Bfs(int s, int t) {
    for (int i = 0; i < max_n; ++i) {
      d[i] = inf;
    }
    d[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
      int cur = q.front();
      q.pop();
      for (int i = 0; i < v[cur].size(); ++i) {
        int ed_ind = v[cur][i];
        edge& e = ed[ed_ind];
        if (e.flow < e.cap && d[e.to] == inf) {
          d[e.to] = d[cur] + 1;
          q.push(e.to);
        }
      }
    }
    return d[t] != inf;
  }
  int Dfs(int cur, int flow, int t) {
    if (cur == t) {
      return flow;
    }
    for (int& i = st[cur]; i < v[cur].size(); ++i) {
      int e_ind = v[cur][i];
      edge& e = ed[e_ind];
      int flow_back = 0;
      if (e.flow < e.cap && d[e.to] == d[cur] + 1) {
        flow_back = Dfs(e.to, min(flow, e.cap - e.flow), t);
      }
      if (flow_back > 0) {
        e.flow += flow_back;
        ed[e_ind ^ 1].flow -= flow_back;
        return flow_back;
      }
    }
    return 0;
  }
  void Clear() {
    for (int i = 0; i < ed.size(); ++i) {
      ed[i].flow = 0;
    }
  }
  long long FindMaxFlow(int s, int t) {
    Clear();
    long long result = 0;
    while (Bfs(s, t)) {
      memset(st, 0, sizeof(st));
      while (int flow = Dfs(s, inf, t)) {
        result += flow;
      }
    }
    return result;
  }
};
struct HomoryHu {
  Dinic dinic;
  vector<pair<int, long long>> tree[max_n];
  int pr[max_n];
  long long max_flow[max_n][max_n];
  int n;
  HomoryHu(int n) : n(n) {}
  void Calculate() {
    for (int i = 0; i < n; ++i) {
      pr[i] = 0;
      max_flow[i][i] = 0;
    }
    for (int i = 1; i < n; ++i) {
      long long flow = dinic.FindMaxFlow(i, pr[i]);
      for (int j = i + 1; j < n; ++j) {
        if (pr[j] == pr[i] && dinic.d[j] != inf) {
          pr[j] = i;
        }
      }
      tree[pr[i]].emplace_back(i, flow);
      tree[i].emplace_back(pr[i], flow);
      for (int j = 0; j < i; ++j) {
        max_flow[j][i] = max_flow[i][j] = min(max_flow[j][pr[i]], flow);
      }
    }
  }
};
vector<pair<int, long long>> v[max_n];
long long sum_edges;
vector<int> per;
int bf, bt;
long long bc;
void dfs(int cur, int pr) {
  for (int i = 0; i < v[cur].size(); ++i) {
    int to = v[cur][i].first;
    int cap = v[cur][i].second;
    if (to == pr) continue;
    if (cap < bc) {
      bc = cap;
      bf = cur;
      bt = to;
    }
    dfs(to, cur);
  }
}
void Solve(int cur) {
  if (v[cur].size() == 0) {
    per.push_back(cur);
    return;
  }
  bf = -1, bt = -1, bc = inf;
  dfs(cur, -1);
  if (bc == inf) {
    exit(228);
  }
  sum_edges += bc;
  for (auto it = v[bf].begin(); it != v[bf].end(); ++it) {
    if (*it == make_pair(bt, bc)) {
      v[bf].erase(it);
      break;
    }
  }
  for (auto it = v[bt].begin(); it != v[bt].end(); ++it) {
    if (*it == make_pair(bf, bc)) {
      v[bt].erase(it);
      break;
    }
  }
  int mybf = bf;
  int mybt = bt;
  Solve(mybf);
  Solve(mybt);
}
int main() {
  int n, m;
  cin >> n >> m;
  HomoryHu homory(n);
  for (int i = 0; i < m; ++i) {
    int from, to, cap;
    cin >> from >> to >> cap;
    --from, --to;
    homory.dinic.AddEdgeIndir(from, to, cap);
  }
  homory.Calculate();
  for (int i = 0; i < n; ++i) {
    v[i] = homory.tree[i];
  }
  Solve(0);
  cout << sum_edges << endl;
  for (int a : per) {
    cout << a + 1 << ' ';
  }
  return 0;
}
