#include <bits/stdc++.h>
using namespace std;
const int MAXN = 210;
const int MAXM = 2100;
const int INF = 1e9;
int n, m;
int color[MAXN];
int tree[MAXN][MAXN];
int who[MAXN];
int reachable[MAXN];
int to[MAXM], cap[MAXM], nxt[MAXM], head[MAXN], E;
int d[MAXN];
int S, T;
vector<pair<int, int> > g[MAXN];
bool was[MAXN];
void addEdge(int a, int b, int c) {
  to[E] = b;
  cap[E] = c;
  nxt[E] = head[a];
  head[a] = E++;
  to[E] = a;
  cap[E] = c;
  nxt[E] = head[b];
  head[b] = E++;
}
bool bfs() {
  for (int i = 1; i <= n; ++i) {
    d[i] = INF;
  }
  d[S] = 0;
  queue<int> q;
  q.push(S);
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int id = head[v]; ~id; id = nxt[id]) {
      if (cap[id] > 0 && d[to[id]] > d[v] + 1) {
        d[to[id]] = d[v] + 1;
        q.push(to[id]);
      }
    }
  }
  return d[T] != INF;
}
int dfs(int v, int flow = INF) {
  if (v == T) return flow;
  int res = 0;
  for (int id = head[v]; ~id; id = nxt[id]) {
    if (cap[id] > 0 && d[to[id]] == d[v] + 1) {
      int pushed = dfs(to[id], min(cap[id], flow));
      if (pushed) {
        cap[id] -= pushed;
        cap[id ^ 1] += pushed;
        res += pushed;
        flow -= pushed;
        if (!flow) break;
      }
    }
  }
  return res;
}
int Dinic() {
  int mf = 0;
  while (bfs()) mf += dfs(S);
  return mf;
}
struct Edge {
  int a, b, c;
  Edge(int a = 0, int b = 0, int c = 0) : a(a), b(b), c(c) {}
} e[MAXM];
void markCut() {
  memset(reachable, 0, sizeof reachable);
  queue<int> q;
  q.push(S);
  reachable[S] = true;
  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int id = head[v]; ~id; id = nxt[id]) {
      if (cap[id] > 0 && !reachable[to[id]]) {
        reachable[to[id]] = true;
        q.push(to[id]);
      }
    }
  }
}
void GomoryHu() {
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      tree[i][j] = INF;
    }
  }
  for (int i = 1; i <= n; ++i) {
    color[i] = 1;
  }
  for (int it = 1; it < n; ++it) {
    for (int i = 1; i <= n; ++i) {
      who[i] = 0;
    }
    for (int i = 1; i <= n; ++i) {
      if (who[color[i]]) {
        S = who[color[i]];
        T = i;
        break;
      }
      who[color[i]] = i;
    }
    memset(head, 0xff, sizeof head);
    E = 0;
    for (int i = 0; i < m; ++i) {
      if (color[e[i].a] == color[e[i].b] && color[e[i].a] != color[S]) continue;
      int u = color[e[i].a] == color[S] ? e[i].a : color[e[i].a];
      int v = color[e[i].b] == color[S] ? e[i].b : color[e[i].b];
      addEdge(u, v, e[i].c);
    }
    int mincut = Dinic();
    markCut();
    vector<pair<int, int> > neighbours;
    for (int i = 1; i <= n; ++i) {
      if (tree[color[S]][i] != INF) {
        neighbours.push_back(make_pair(i, tree[color[S]][i]));
        tree[color[S]][i] = tree[i][color[S]] = INF;
      }
    }
    for (int i = 0; i < (int)neighbours.size(); ++i) {
      if (reachable[neighbours[i].first]) {
        tree[S][neighbours[i].first] = tree[neighbours[i].first][S] =
            neighbours[i].second;
      } else {
        tree[T][neighbours[i].first] = tree[neighbours[i].first][T] =
            neighbours[i].second;
      }
    }
    tree[S][T] = tree[T][S] = mincut;
    int col = color[S];
    for (int i = 1; i <= n; ++i) {
      if (color[i] == col) {
        if (reachable[i])
          color[i] = S;
        else
          color[i] = T;
      }
    }
  }
}
pair<int, int> go(int v, int p) {
  pair<int, int> res(-1, -1);
  for (int i = 0; i < (int)g[v].size(); ++i) {
    if (g[v][i].first == p || was[g[v][i].first]) continue;
    if (res.first == -1 || g[v][i].second < tree[res.first][res.second])
      res = make_pair(v, g[v][i].first);
    pair<int, int> cur = go(g[v][i].first, v);
    if (res.first == -1)
      res = cur;
    else if (cur.first != -1 &&
             tree[res.first][res.second] > tree[cur.first][cur.second]) {
      res = cur;
    }
  }
  return res;
}
vector<int> calc(int v, int par) {
  pair<int, int> lightest = go(v, par);
  if (lightest.first == -1) return vector<int>(1, v);
  was[lightest.second] = true;
  vector<int> lt = calc(lightest.first, lightest.second);
  was[lightest.second] = false;
  was[lightest.first] = true;
  vector<int> rt = calc(lightest.second, lightest.first);
  was[lightest.second] = true;
  for (int i = 0; i < (int)rt.size(); ++i) lt.push_back(rt[i]);
  return lt;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    cin >> e[i].a >> e[i].b >> e[i].c;
  }
  GomoryHu();
  int res = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
      if (tree[i][j] != INF) {
        res += tree[i][j];
        g[i].push_back(make_pair(j, tree[i][j]));
        g[j].push_back(make_pair(i, tree[i][j]));
      }
    }
  }
  cout << res << endl;
  vector<int> p = calc(1, -1);
  for (auto it : p) {
    cout << it << ' ';
  }
  return 0;
}
