#include <bits/stdc++.h>   using namespace std;   const long long oo = 0x3f3f3f3f3f3f3f3fLL;   struct Edge {     int u, v;     long long cap[2], flow;   };   vector<int> d, act;   bool bfs(int s, int t, vector<vector<int>>& adj, vector<Edge>& E,            long long lim = 1) {     queue<int> Q;     d = vector<int>(adj.size(), -1);     d[t] = 0;     Q.push(t);     for (Q.push(t); Q.size() and d[s] == -1; Q.pop()) {       int u = Q.front();       for (int i = (0); i < int(adj[u].size()); i++) {         int e = adj[u][i], v = (E[e].u ^ E[e].v ^ u);         if (((E[e].u == v) ? E[e].cap[0] - E[e].flow : E[e].cap[1] + E[e].flow) >=                 lim and             d[v] == -1) {           d[v] = d[u] + 1;           Q.push(v);         }       }     }     return d[s] >= 0;   }   long long dfs(int u, int t, long long bot, vector<vector<int>>& adj,                 vector<Edge>& E) {     if (bot == 0) return 0;     if (u == t) return bot;     for (; act[u] < int(adj[u].size()); ++act[u]) {       int e = adj[u][act[u]];       if (d[u] == d[(E[e].u ^ E[e].v ^ u)] + 1) {         long long inc = dfs((E[e].u ^ E[e].v ^ u), t,                             min(bot, ((E[e].u == u) ? E[e].cap[0] - E[e].flow                                                     : E[e].cap[1] + E[e].flow)),                             adj, E);         if (inc) {           E[e].flow += ((E[e].u == u) ? (inc) : (-(inc)));           return inc;         }       }     }     return 0;   }   long long maxflow(int s, int t, vector<vector<int>>& adj, vector<Edge>& E,                     int F = 0) {     for (auto& e : E) e.flow = 0;     long long flow = 0, bot;     for (int lim = (1 << F); lim >= 1; lim >>= 1) {       while (bfs(s, t, adj, E, lim)) {         act = vector<int>(adj.size(), 0);         while ((bot = dfs(s, t, oo, adj, E))) flow += bot;       }     }     return flow;   }   inline void addEdge(int x, int y, vector<vector<int>>& adj, vector<Edge>& E,                       long long c, long long rc = 0) {     Edge e;     e.u = x;     e.v = y;     e.flow = 0;     e.cap[0] = c;     e.cap[1] = rc;     adj[x].push_back(int((E).size()));     adj[y].push_back(int((E).size()));     E.push_back(e);   }   long long anss = 0;   void gomory_hu(vector<vector<int>>& adj, vector<Edge>& E, vector<int>& parent,                  vector<vector<long long>>& ans) {     int n = int((adj).size());     parent.assign(n, 0);     ans.assign(n, vector<long long>(n, oo));     for (int i = (1); i < int(n); i++) {       long long f = maxflow(i, parent[i], adj, E);       anss += f;       bfs(i, parent[i], adj, E);       for (int j = (i + 1); j < int(n); j++)         if (d[j] == -1 and parent[j] == parent[i]) parent[j] = i;       ans[i][parent[i]] = ans[parent[i]][i] = f;       for (int j = (0); j < int(i); j++)         ans[i][j] = ans[j][i] = min(f, ans[parent[i]][j]);     }   }   int main() {     ios::sync_with_stdio(0);     cin.tie(0);     int n, m;     cin >> n >> m;     vector<vector<int>> adj(n);     vector<Edge> E;     for (int i = (0); i < int(m); i++) {       int a, b, c;       cin >> a >> b >> c;       --a, --b;       addEdge(a, b, adj, E, c, c);     }     vector<int> par;     vector<vector<long long>> d;     gomory_hu(adj, E, par, d);     cout << anss << endl;     int best = 0;     vector<int> res(n);     for (int i = 0; i < n; ++i) {       res[i] = i;     }     for (int i = 0; i < 1; ++i) {       vector<int> order;       order.push_back(i);       vector<int> used(n, 0);       used[i] = true;       int score = 0;       while (int((order).size()) != n) {         int best = -1, index = -1;         for (int j = 0; j < n; ++j) {           if (!used[j] && d[order.back()][j] > best) {             best = d[order.back()][j];             index = j;           }         }         score += best;         order.push_back(index);         used[index] = true;       }       if (score > best) {         best = score;         res = order;       }     }     for (int i = 0; i < res.size(); ++i) {       printf( %d  , res[i] + 1);     }     printf(  n );   }   