#include <bits/stdc++.h>
using namespace std;
struct edge {
  int from, to, cap, flow;
};
struct Dinic {
  int n, m, s, t;
  vector<edge> E;
  vector<int> G[210];
  bool vis[210];
  int dis[210];
  void clear_graph() {
    E.clear();
    for (int i = 0; i < 210; ++i) G[i].clear();
  }
  void clear_flow() {
    for (int i = 0; i < E.size(); ++i) E[i].flow = 0;
  }
  void addedge(int from, int to, int cap) {
    E.push_back((edge){from, to, cap, 0});
    E.push_back((edge){to, from, cap, 0});
    int s = E.size();
    G[from].push_back(s - 2);
    G[to].push_back(s - 1);
  }
  bool BFS() {
    memset(vis, 0, sizeof(vis));
    queue<int> Q;
    Q.push(s);
    vis[s] = 1;
    dis[s] = 0;
    while (!Q.empty()) {
      int t = Q.front();
      Q.pop();
      for (int i = 0; i < G[t].size(); ++i) {
        edge &e = E[G[t][i]];
        if (!vis[e.to] && e.cap > e.flow) {
          vis[e.to] = 1;
          dis[e.to] = dis[e.from] + 1;
          Q.push(e.to);
        }
      }
    }
    return vis[t];
  }
  int DFS(int x, int a) {
    if (x == t || !a) return a;
    int flow = 0, f;
    for (int i = 0; i < G[x].size(); ++i) {
      edge &e = E[G[x][i]];
      if (dis[e.from] + 1 == dis[e.to] &&
          (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
        e.flow += f;
        E[G[x][i] ^ 1].flow -= f;
        flow += f;
        a -= f;
        if (!a) break;
      }
    }
    return flow;
  }
  int exec(int s, int t) {
    this->s = s;
    this->t = t;
    int flow = 0;
    while (BFS()) flow += DFS(s, 0x3f3f3f3f);
    return flow;
  }
} dinic;
int n, m;
int fa[210], falen[210];
int now;
int ans = 0;
void build_tree() {
  for (int i = 1; i <= n; ++i) fa[i] = 1;
  for (int i = 2; i <= n; ++i) {
    dinic.clear_flow();
    falen[i] = dinic.exec(i, fa[i]);
    dinic.BFS();
    for (int j = i + 1; j <= n; ++j)
      if (dinic.vis[j] && fa[j] == fa[i]) fa[j] = i;
  }
  dinic.clear_graph();
  for (int i = 2; i <= n; ++i) {
    dinic.addedge(i, fa[i], falen[i]);
    ans += falen[i];
  }
}
void find_min(int x, int pre) {
  for (int i = 0; i < dinic.G[x].size(); ++i) {
    edge &e = dinic.E[dinic.G[x][i]];
    if (e.to != pre && e.cap != -1) {
      if (now == -1 || e.cap < dinic.E[now].cap) now = dinic.G[x][i];
      find_min(e.to, x);
    }
  }
}
void solve(int x) {
  now = -1;
  find_min(x, 0);
  if (now == -1) {
    printf("%d ", x);
    return;
  }
  dinic.E[now].cap = dinic.E[now ^ 1].cap = -1;
  int p = now;
  solve(dinic.E[p].from);
  solve(dinic.E[p].to);
}
void output() {
  printf("%d\n", ans);
  solve(1);
  puts("");
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; ++i) {
    int u, v, w;
    scanf("%d%d%d", &u, &v, &w);
    dinic.addedge(u, v, w);
  }
  build_tree();
  output();
  return 0;
}
