#include <bits/stdc++.h>

using namespace std;

int main(int argc, char** argv) {
  ifstream cin("hamilton.in");
  ofstream cout("hamilton.out");

  int n, m; cin >> n >> m;

  vector<vector<int>> dist(n, vector<int>(n, 1e9));
  for (int i = 0; i < n; ++i) 
    dist[i][i] = 0;
  for (int i = 0; i < m; ++i) {
    int a, b, c; cin >> a >> b >> c;
    dist[a][b] = c;
  }

  string algo = "astar"; 
  // argv[1];
    
  vector<int> solution;
  int best = 1e9;
  
  if (algo == "naive") {
    vector<int> order(n);
    for (int i = 0; i < n; ++i)
      order[i] = i;
      
    do {
      int ans = 0;
      for (int j = n - 1, i = 0; i < n; j = i++) {
        ans += dist[order[j]][order[i]];
        if (ans > best) break;
      }
      if (best > ans) {
        best = ans;
        solution = order;
      }
    } while (next_permutation(order.begin(), order.end()));
  } else {
    vector<vector<int>> dp(1 << n, vector<int>(n, 1e9));
    vector<vector<int>> choose(1 << n, vector<int>(n, -1));
    int msk = (1 << n) - 1, last = -1;
    dp[1 << 0][0] = 0;
    
    if (algo == "dp") {
      for (int msk = 0; msk < (1 << n); ++msk) {
        for (int node = 0; node < n; ++node) {
          if (!(msk & (1 << node))) continue;
          for (int vec = 0; vec < n; ++vec) {
            if (msk & (1 << vec)) continue;
            int nmsk = (msk | (1 << vec));
            if (dp[nmsk][vec] > dp[msk][node] + dist[node][vec]) {
              dp[nmsk][vec] = dp[msk][node] + dist[node][vec];
              choose[nmsk][vec] = node;
            }
          }
        }
      }
      for (int i = 1; i < n; ++i) {
        int now = dp[msk][i] + dist[i][0];
        if (best > now) {
          best = now;
          last = i;
        }
      }
    } else if (algo == "astar") {
      auto rf = dist;
      for (int k = 0; k < n; ++k)
        for (int i = 0; i < n; ++i)
          for (int j = 0; j < n; ++j) 
            if (rf[i][j] > rf[i][k] + rf[k][j])
              rf[i][j] = rf[i][k] + rf[k][j];
      
      vector<vector<int>> h(1 << n, vector<int>(n, -1));

      auto calc_h = [&](int msk, int node) {
        if (h[msk][node] != -1) return h[msk][node];

        if (msk == (1 << n) - 1)
          return dist[node][0];

        int ans = 0;
        for (int k = 0; k < n; ++k) {
          if (msk & (1 << k)) continue;
          ans = max(ans, rf[node][k] + rf[k][0]);
        }
        return h[msk][node] = ans;
      };
    
      priority_queue<tuple<int, int, int>> pq;
      pq.emplace(-calc_h(1 << 0, 0), (1 << 0), 0);
      while (!pq.empty()) {
        int d, msk, node; tie(d, msk, node) = pq.top(); 
        pq.pop(); d = -d;

        if (d > dp[msk][node] + calc_h(msk, node)) 
          continue;

        if (msk == (1 << n) - 1) {
          best = d;
          last = node;
          break;
        }


        for (int vec = 0; vec < n; ++vec) {
          if (msk & (1 << vec)) continue;
          int nmsk = (msk | (1 << vec));
          if (dp[nmsk][vec] > dp[msk][node] + dist[node][vec]) {
            dp[nmsk][vec] = dp[msk][node] + dist[node][vec];
            choose[nmsk][vec] = node;
            pq.emplace(-(dp[nmsk][vec] + calc_h(nmsk, vec)), nmsk, vec);
          }
        }
      }
    }

    cerr << "BEST: " << best << endl;
    solution = {0};
    for (int it = 1; it < n; ++it) {
      solution.push_back(last);
      int n_last = choose[msk][last];
      msk ^= (1 << last);
      last = n_last;
    }
  }

  if (last == -1) {
    cout << "Nu exista solutie\n";
    return 0;
  }

  cout << best << endl;
  
  for (int i = 0; i < n; ++i)
    cout << solution[i] << " ";
  cout << endl;
  
  return 0;
}