#include <bits/stdc++.h>
using namespace std;
long long pwr(long long base, long long p, long long mod = (1000000007LL)) {
  long long ans = 1;
  while (p) {
    if (p & 1) ans = (ans * base) % mod;
    base = (base * base) % mod;
    p /= 2;
  }
  return ans;
}
struct edge {
  int a, b, cap, flow;
  edge() {}
  edge(int a, int b, int cap, int flow) {
    this->a = a;
    this->b = b;
    this->cap = cap;
    this->flow = flow;
  }
};
const int N = 500;
int src, sink, dist[N], ptr[N];
vector<edge> edge_list;
vector<int> adj_list[N];
void add_edge(int a, int b, int cap) {
  adj_list[a].push_back((int)edge_list.size());
  edge_list.push_back(edge(a, b, cap, 0));
  adj_list[b].push_back((int)edge_list.size());
  edge_list.push_back(edge(b, a, cap, 0));
}
bool bfs() {
  memset(dist, -1, sizeof(dist));
  queue<int> qq;
  dist[src] = 0;
  qq.push(src);
  while (!qq.empty()) {
    int v = qq.front();
    qq.pop();
    for (auto id : adj_list[v]) {
      int vv = edge_list[id].b;
      if (dist[vv] == -1 && edge_list[id].flow < edge_list[id].cap) {
        qq.push(vv);
        dist[vv] = dist[v] + 1;
      }
    }
  }
  return (dist[sink] != -1);
}
int dfs(int v, int flow) {
  if (v == sink || flow == 0) return flow;
  for (; ptr[v] < (int)adj_list[v].size(); ptr[v]++) {
    int id = adj_list[v][ptr[v]];
    int to = edge_list[id].b;
    if (dist[to] != dist[v] + 1) continue;
    int pushed = dfs(to, min(flow, edge_list[id].cap - edge_list[id].flow));
    if (pushed) {
      edge_list[id].flow += pushed;
      edge_list[1 ^ id].flow -= pushed;
      return pushed;
    }
  }
  return 0;
}
int n, e, compcnt, comp_idx[N], adj_mat[N][N], cnt[N], temp_comp[N];
vector<pair<int, pair<int, int> > > edges;
vector<int> original_adj[N];
int dinitz() {
  edge_list.clear();
  for (int i = 0; i <= 2 * n; i++) adj_list[i].clear();
  for (int i = 1; i <= 2 * n; i++)
    for (int j = i + 1; j <= 2 * n; j++)
      if (adj_mat[i][j] > 0) {
        add_edge(i, j, adj_mat[i][j]);
      }
  int ans = 0;
  while (1) {
    if (!bfs()) break;
    memset(ptr, 0, sizeof(ptr));
    while (int pushed = dfs(src, (1000000007LL))) ans += pushed;
  }
  return ans;
}
int validate_dinitz() {
  edge_list.clear();
  for (int i = 0; i <= 2 * n; i++) adj_list[i].clear();
  for (auto e : edges) add_edge(e.second.first, e.second.second, e.first);
  int ans = 0;
  while (1) {
    if (!bfs()) break;
    memset(ptr, 0, sizeof(ptr));
    while (int pushed = dfs(src, (1000000007LL))) ans += pushed;
  }
  return ans;
}
set<pair<int, int> > gomory_hu_adj[N];
bool present[N];
int reverse_comp_idx[N];
vector<int> members[N];
void create_component(int v, int cidx, int banned, bool debug) {
  temp_comp[v] = cidx;
  for (auto vv : gomory_hu_adj[v]) {
    if (vv.first != banned && temp_comp[vv.first] == -1)
      create_component(vv.first, cidx, banned, debug);
  }
}
void gomory_hu_algo() {
  if (compcnt == n) return;
  memset(cnt, 0, sizeof(cnt));
  memset(adj_mat, 0, sizeof(adj_mat));
  memset(present, 0, sizeof(present));
  src = sink = -1;
  int selected_comp = -1;
  for (int i = 1; i <= n; i++) {
    cnt[comp_idx[i]]++;
    if (cnt[comp_idx[i]] > 1) selected_comp = comp_idx[i];
  }
  for (int i = 1; i <= n; i++) members[i].clear();
  for (int i = 1; i <= n; i++) {
    if (comp_idx[i] == selected_comp) {
      if (src == -1)
        src = i;
      else
        sink = i;
      present[i] = true;
    } else {
      present[n + comp_idx[i]] = true;
    }
    members[comp_idx[i]].push_back(i);
  }
  assert(selected_comp != -1);
  memset(temp_comp, -1, sizeof(temp_comp));
  int z = 0;
  for (int i = 1; i <= compcnt; i++)
    if (temp_comp[i] == -1 && i != selected_comp)
      create_component(i, ++z, selected_comp, (compcnt == 3));
  for (auto e : edges) {
    int a = e.second.first, b = e.second.second, c = e.first;
    if (comp_idx[a] == comp_idx[b]) {
      if (comp_idx[a] == selected_comp) {
        adj_mat[a][b] = adj_mat[b][a] = c;
      }
      continue;
    }
    if (comp_idx[a] != selected_comp && comp_idx[b] != selected_comp) {
      adj_mat[n + temp_comp[comp_idx[a]]][n + temp_comp[comp_idx[b]]] += c;
      adj_mat[n + temp_comp[comp_idx[b]]][n + temp_comp[comp_idx[a]]] += c;
      continue;
    }
    if (comp_idx[b] == selected_comp) swap(a, b);
    adj_mat[a][n + temp_comp[comp_idx[b]]] += c;
    adj_mat[n + temp_comp[comp_idx[b]]][a] += c;
  }
  int flow = dinitz();
  bfs();
  compcnt++;
  for (int i = 1; i <= n; i++)
    if (comp_idx[i] == selected_comp && dist[i] == -1) comp_idx[i] = compcnt;
  set<pair<int, int> >::iterator it = gomory_hu_adj[selected_comp].begin();
  while (it != gomory_hu_adj[selected_comp].end()) {
    int other = (*it).first, val = (*it).second;
    if (dist[n + temp_comp[other]] == -1) {
      it = gomory_hu_adj[selected_comp].erase(it);
      gomory_hu_adj[other].erase({selected_comp, val});
      gomory_hu_adj[compcnt].insert({other, val});
      gomory_hu_adj[other].insert({compcnt, val});
      continue;
    }
    it++;
  }
  gomory_hu_adj[selected_comp].insert({compcnt, flow});
  gomory_hu_adj[compcnt].insert({selected_comp, flow});
  gomory_hu_algo();
}
bool involved[N], marked[N];
void mark(int v, int last) {
  marked[v] = true;
  for (auto it : gomory_hu_adj[v]) {
    if (involved[it.first] && it.first != last) mark(it.first, v);
  }
}
void print(vector<int> &arr) {
  for (auto it : arr) cout << it << " ";
}
vector<int> generate_permutation(vector<int> vertices) {
  if ((int)vertices.size() == 1) return vertices;
  memset(involved, 0, sizeof(involved));
  memset(marked, 0, sizeof(marked));
  for (auto v : vertices) {
    involved[v] = true;
    marked[v] = false;
  }
  int minedge = (1000000007LL), v1 = -1, v2 = -1;
  for (auto v : vertices) {
    if (!involved[v]) continue;
    for (auto it : gomory_hu_adj[v])
      if (involved[it.first] && it.second < minedge) {
        minedge = it.second;
        v1 = v;
        v2 = it.first;
      }
  }
  mark(v1, v2);
  vector<int> A, B;
  for (auto v : vertices)
    if (marked[v])
      A.push_back(v);
    else
      B.push_back(v);
  vector<int> ans_A = generate_permutation(A);
  vector<int> ans_B = generate_permutation(B);
  ans_A.insert(ans_A.end(), ans_B.begin(), ans_B.end());
  return ans_A;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> e;
  for (int i = 0; i < e; i++) {
    int a, b, c;
    cin >> a >> b >> c;
    edges.push_back({c, {a, b}});
    original_adj[a].push_back(b);
    original_adj[b].push_back(a);
  }
  compcnt = 1;
  for (int i = 1; i <= n; i++) comp_idx[i] = 1;
  gomory_hu_algo();
  for (int i = 1; i <= n; i++) reverse_comp_idx[comp_idx[i]] = i;
  int ans = 0;
  for (int i = 1; i <= n; i++)
    for (auto it : gomory_hu_adj[i]) ans += it.second;
  ans /= 2;
  cout << ans << endl;
  vector<int> vertices;
  for (int i = 1; i <= n; i++) vertices.push_back(i);
  vector<int> permutation = generate_permutation(vertices);
  for (auto it : permutation) cout << reverse_comp_idx[it] << " ";
  return 0;
}
