#include <bits/stdc++.h>
using namespace std;
const int inf = 1 << 30;
struct Edge {
  int u, v, w;
} e[1002];
int head[202], ver[1002 * 4], nxt[1002 * 4], cap[1002 * 4], l;
int head1[202], ver1[202 * 2], nxt1[202 * 2], edge1[202 * 2], l1;
int n, m, i, a[202], tmp1[202], tmp2[202], dis[202], S, T, ans,
    minx = inf, s, t, id, poi[202], num;
bool use[202 * 2], vis[202];
int read() {
  char c = getchar();
  int w = 0;
  while (c < '0' || c > '9') c = getchar();
  while (c <= '9' && c >= '0') {
    w = w * 10 + c - '0';
    c = getchar();
  }
  return w;
}
void insert(int x, int y, int z) {
  ver[l] = y;
  cap[l] = z;
  nxt[l] = head[x];
  head[x] = l;
  l++;
  ver[l] = x;
  cap[l] = 0;
  nxt[l] = head[y];
  head[y] = l;
  l++;
}
void insert1(int x, int y, int z) {
  ver1[l1] = y;
  edge1[l1] = z;
  nxt1[l1] = head1[x];
  head1[x] = l1;
  l1++;
}
bool bfs() {
  queue<int> q;
  memset(dis, -1, sizeof(dis));
  q.push(S);
  dis[S] = 0;
  while (!q.empty()) {
    int x = q.front();
    q.pop();
    for (int i = head[x]; i != -1; i = nxt[i]) {
      int y = ver[i];
      if (dis[y] == -1 && cap[i] > 0) {
        dis[y] = dis[x] + 1;
        q.push(y);
      }
    }
  }
  return (dis[T] > 0);
}
int dfs(int x, int flow) {
  if (x == T || flow == 0) return flow;
  int ans = 0;
  for (int i = head[x]; i != -1; i = nxt[i]) {
    int y = ver[i];
    if (dis[y] == dis[x] + 1 && cap[i] > 0) {
      int a = dfs(y, min(flow, cap[i]));
      flow -= a;
      ans += a;
      cap[i] -= a;
      cap[i ^ 1] += a;
    }
    if (flow == 0) break;
  }
  if (flow) dis[x] = -inf;
  return ans;
}
int Dinic() {
  int ans = 0;
  memset(head, -1, sizeof(head));
  l = 0;
  for (int i = 1; i <= m; i++) {
    insert(e[i].u, e[i].v, e[i].w);
    insert(e[i].v, e[i].u, e[i].w);
  }
  while (bfs()) ans += dfs(S, inf);
  return ans;
}
void build(int l, int r) {
  if (l == r) return;
  S = a[l], T = a[l + 1];
  int ans = Dinic(), cnt1 = 0, cnt2 = 0;
  insert1(S, T, ans);
  insert1(T, S, ans);
  for (int i = l; i <= r; i++) {
    if (dis[a[i]] == -1)
      tmp2[++cnt2] = a[i];
    else
      tmp1[++cnt1] = a[i];
  }
  for (int i = l; i <= l + cnt1 - 1; i++) a[i] = tmp1[i - l + 1];
  for (int i = l + cnt1; i <= r; i++) a[i] = tmp2[i - l - cnt1 + 1];
  build(l, l + cnt1 - 1);
  build(l + cnt1, r);
}
void cal(int x, int pre) {
  for (int i = head1[x]; i != -1; i = nxt1[i]) {
    int y = ver1[i];
    if (y != pre) {
      ans += edge1[i];
      if (edge1[i] < minx) minx = edge1[i], s = x, t = y, id = i;
      cal(y, x);
    }
  }
}
int my_comp(const int &x, const int &y) { return edge1[x] > edge1[y]; }
void find(int x, int pre) {
  for (int i = head1[x]; i != -1; i = nxt1[i]) {
    int y = ver1[i];
    if (y != pre && !vis[i]) {
      if (edge1[i] < minx) minx = edge1[i], s = x, t = y, id = i;
      find(y, x);
    }
  }
}
void print(int x) {
  minx = inf, s = t = 0;
  find(x, 0);
  if (s == 0) {
    poi[++num] = x;
    return;
  }
  int p = s, q = t;
  vis[id] = vis[id ^ 1] = 1;
  print(p);
  print(q);
}
int main() {
  memset(head1, -1, sizeof(head1));
  n = read();
  m = read();
  for (i = 1; i <= m; i++) e[i].u = read(), e[i].v = read(), e[i].w = read();
  for (i = 1; i <= n; i++) a[i] = i;
  build(1, n);
  cal(1, 0);
  printf("%d\n", ans);
  int l = s, r = t;
  vis[id] = vis[id ^ 1] = 1;
  print(l);
  print(r);
  for (i = 1; i <= n; i++) printf("%d ", poi[i]);
  puts("");
  return 0;
}
