#include <bits/stdc++.h>
using namespace std;
const int maxn = 200 + 10;
const int INF = 1000000000;
int ans[maxn][maxn], cur[maxn], dis[maxn], vis[maxn], a[maxn], flag[maxn],
    t1[maxn], t2[maxn];
int n, m, s, t, tot, path[maxn], anspath[maxn];
struct edge {
  int from, to, cap, flow;
};
struct node {
  int u, v, c;
} e[1010];
struct edge1 {
  int from, to, cost, flow;
};
vector<edge1> edges1;
vector<edge> edges;
vector<int> g[maxn];
void addedge(int from, int to, int cap) {
  edges.push_back((edge){from, to, cap, 0});
  edges.push_back((edge){to, from, 0, 0});
  int m1 = edges.size();
  g[from].push_back(m1 - 2);
  g[to].push_back(m1 - 1);
}
void pre() {
  edges.clear();
  for (int i = 1; i <= n; i++) g[i].clear();
  for (int i = 1; i <= m; i++) {
    addedge(e[i].u, e[i].v, e[i].c);
    addedge(e[i].v, e[i].u, e[i].c);
  }
}
bool bfs() {
  memset(vis, 0, sizeof(vis));
  queue<int> Q;
  Q.push(s);
  vis[s] = 1;
  dis[s] = 0;
  while (!Q.empty()) {
    int x = Q.front();
    Q.pop();
    for (int i = 0; i < g[x].size(); i++) {
      edge e = edges[g[x][i]];
      if (e.cap > e.flow && !vis[e.to]) {
        dis[e.to] = dis[x] + 1;
        vis[e.to] = 1;
        Q.push(e.to);
      }
    }
  }
  return vis[t];
}
int dfs(int x, int a) {
  if (x == t || a == 0) return a;
  int flow = 0, f;
  for (int &i = cur[x]; i < g[x].size(); i++) {
    edge &e = edges[g[x][i]];
    if (dis[e.to] == dis[x] + 1 &&
        (f = dfs(e.to, min(e.cap - e.flow, a))) > 0) {
      flow += f;
      e.flow += f;
      edges[g[x][i] ^ 1].flow -= f;
      a -= f;
      if (a == 0) break;
    }
  }
  return flow;
}
int maxflow() {
  int flow = 0;
  while (bfs()) {
    memset(cur, 0, sizeof(cur));
    flow += dfs(s, INF);
  }
  return flow;
}
void work() {
  memset(flag, 0, sizeof(flag));
  queue<int> Q;
  Q.push(s);
  flag[s] = 1;
  while (!Q.empty()) {
    int x = Q.front();
    Q.pop();
    for (int i = 0; i < g[x].size(); i++) {
      edge e = edges[g[x][i]];
      int v = e.to;
      if (e.cap > e.flow && !flag[v]) {
        flag[v] = 1;
        Q.push(v);
      }
    }
  }
}
void solve(int l, int r) {
  if (l >= r) return;
  pre();
  s = a[l], t = a[r];
  int res = maxflow();
  work();
  for (int i = 1; i <= n; i++)
    if (flag[i])
      for (int j = 1; j <= n; j++)
        if (!flag[j] && i != j) {
          ans[i][j] = min(ans[i][j], res);
          ans[j][i] = min(ans[j][i], res);
        }
  int tot1 = 0, tot2 = 0;
  for (int i = l; i <= r; i++)
    if (!flag[a[i]])
      t1[++tot1] = a[i];
    else
      t2[++tot2] = a[i];
  for (int i = l; i <= l + tot1 - 1; i++) a[i] = t1[i - l + 1];
  for (int i = l + tot1; i <= r; i++) a[i] = t2[i - l - tot1 + 1];
  solve(l, l + tot1 - 1);
  solve(l + tot1, r);
}
int main() {
  scanf("%d%d", &n, &m);
  memset(ans, 127 / 2, sizeof(ans));
  for (int i = 1; i <= m; i++) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].c);
  for (int i = 1; i <= n; i++) a[i] = i;
  solve(1, n);
  int out = 0;
  for (int i = 1; i <= n; i++) {
    memset(vis, 0, sizeof(vis));
    vis[i] = 1;
    int now = i, res = 0;
    path[1] = now;
    for (int j = 1; j < n; j++) {
      int maxi = 0, maxj;
      for (int k = 1; k <= n; k++)
        if (!vis[k] && ans[now][k] > maxi) {
          maxi = ans[now][k];
          maxj = k;
        }
      res += maxi;
      vis[maxj] = 1;
      now = maxj;
      path[j + 1] = now;
    }
    if (res > out) {
      for (int j = 1; j <= n; j++) anspath[j] = path[j];
      out = res;
    }
  }
  printf("%d\n", out);
  for (int i = 1; i <= n; i++) printf("%d ", anspath[i]);
  return 0;
}
