#include <bits/stdc++.h>
using namespace std;
template <typename T>
class flow_graph {
 public:
  static constexpr T eps = (T)1e-9;
  struct edge {
    int to;
    T c;
    T f;
    int rev;
  };
  vector<vector<edge> > g;
  vector<int> ptr;
  vector<int> d;
  vector<int> q;
  vector<int> cnt_on_layer;
  vector<int> prev_edge;
  bool can_reach_sink;
  int n;
  int st, fin;
  T flow;
  flow_graph(int n, int st, int fin) : n(n), st(st), fin(fin) {
    assert(0 <= st && st < n && 0 <= fin && fin < n && st != fin);
    g.resize(n);
    ptr.resize(n);
    d.resize(n);
    q.resize(n);
    cnt_on_layer.resize(n + 1);
    prev_edge.resize(n);
    flow = 0;
  }
  void clear_flow() {
    for (int i = 0; i < n; i++) {
      for (edge &e : g[i]) {
        e.f = 0;
      }
    }
    flow = 0;
  }
  void add(int from, int to, T forward_cap, T backward_cap) {
    assert(0 <= from && from < n && 0 <= to && to < n);
    int from_size = g[from].size();
    int to_size = g[to].size();
    g[from].push_back({to, forward_cap, 0, to_size});
    g[to].push_back({from, backward_cap, 0, from_size});
  }
  bool expath() {
    fill(d.begin(), d.end(), n);
    q[0] = fin;
    d[fin] = 0;
    fill(cnt_on_layer.begin(), cnt_on_layer.end(), 0);
    cnt_on_layer[n] = n - 1;
    cnt_on_layer[0] = 1;
    int beg = 0, end = 1;
    while (beg < end) {
      int i = q[beg++];
      for (const edge &e : g[i]) {
        const edge &back = g[e.to][e.rev];
        if (back.c - back.f > eps && d[e.to] == n) {
          cnt_on_layer[d[e.to]]--;
          d[e.to] = d[i] + 1;
          cnt_on_layer[d[e.to]]++;
          q[end++] = e.to;
        }
      }
    }
    return (d[st] != n);
  }
  T augment(int &v) {
    T cur = numeric_limits<T>::max();
    int i = fin;
    while (i != st) {
      const edge &e = g[i][prev_edge[i]];
      const edge &back = g[e.to][e.rev];
      cur = min(cur, back.c - back.f);
      i = e.to;
    }
    i = fin;
    while (i != st) {
      edge &e = g[i][prev_edge[i]];
      edge &back = g[e.to][e.rev];
      back.f += cur;
      e.f -= cur;
      i = e.to;
      if (back.c - back.f <= eps) {
        v = i;
      }
    }
    return cur;
  }
  int retreat(int v) {
    int new_dist = n - 1;
    for (const edge &e : g[v]) {
      if (e.c - e.f > eps && d[e.to] < new_dist) {
        new_dist = d[e.to];
      }
    }
    cnt_on_layer[d[v]]--;
    if (cnt_on_layer[d[v]] == 0) {
      if (new_dist + 1 > d[v]) {
        can_reach_sink = false;
      }
    }
    d[v] = new_dist + 1;
    cnt_on_layer[d[v]]++;
    if (v != st) {
      v = g[v][prev_edge[v]].to;
    }
    return v;
  }
  T max_flow() {
    can_reach_sink = true;
    for (int i = 0; i < n; i++) {
      ptr[i] = (int)g[i].size() - 1;
    }
    if (expath()) {
      int v = st;
      while (d[st] < n) {
        while (ptr[v] >= 0) {
          const edge &e = g[v][ptr[v]];
          if (e.c - e.f > eps && d[e.to] == d[v] - 1) {
            prev_edge[e.to] = e.rev;
            v = e.to;
            if (v == fin) {
              flow += augment(v);
            }
            break;
          }
          ptr[v]--;
        }
        if (ptr[v] < 0) {
          ptr[v] = (int)g[v].size() - 1;
          v = retreat(v);
          if (!can_reach_sink) {
            break;
          }
        }
      }
    }
    return flow;
  }
  vector<bool> min_cut() {
    max_flow();
    assert(!expath());
    vector<bool> ret(n);
    for (int i = 0; i < n; i++) {
      ret[i] = (d[i] != n);
    }
    return ret;
  }
};
int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  flow_graph<int> g(n, 0, 1);
  for (int i = 0; i < m; i++) {
    int x, y, z;
    scanf("%d %d %d", &x, &y, &z);
    x--;
    y--;
    g.add(x, y, z, z);
  }
  vector<vector<int> > a(n, vector<int>(n, 0));
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      g.clear_flow();
      g.st = i;
      g.fin = j;
      a[i][j] = a[j][i] = g.max_flow();
    }
  }
  vector<bool> used(n, false);
  vector<int> ans(1, 0);
  used[ans[0]] = true;
  int sum = 0;
  for (int it = 0; it < n - 1; it++) {
    int best = -1, id = -1;
    for (int i = 0; i < n; i++) {
      if (!used[i] && a[ans.back()][i] > best) {
        best = a[ans.back()][i];
        id = i;
      }
    }
    used[id] = true;
    ans.push_back(id);
    sum += best;
  }
  printf("%d\n", sum);
  for (int i = 0; i < n; i++) {
    if (i > 0) {
      putchar(' ');
    }
    printf("%d", ans[i] + 1);
  }
  printf("\n");
  return 0;
}
