#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int max_dist;
bool used[10][10];
vector<int> answer_path;
vector<int> path;
vector<pair<int, int> > edges[10];

void dfs(int k, int dist)
{
  path.push_back(k);
  bool end = true;
  for (int i = 0; i < (int)edges[k].size(); ++i) {
    int t = edges[k][i].first;
    if (used[k][t])
      continue;
    used[k][t] = used[t][k] = true;
    dfs(edges[k][i].first, dist + edges[k][i].second);
    used[k][t] = used[t][k] = false;
    end = false;
  }

  if (end) {
    if (dist > max_dist) {
      max_dist = dist;
      answer_path = path;
    }
  }
  path.pop_back();
}

int main()
{
  int n, m;
  while (scanf("%d%d", &n, &m), n|m) {
    for (int i = 0; i < n; ++i) {
      edges[i].clear();
    }

    for (int i = 0; i < m; ++i) {
      int a, b, d;
      scanf("%d%d%d", &a, &b, &d);
      --a, --b;
      edges[a].push_back(make_pair(b, d));
      edges[b].push_back(make_pair(a, d));
    }

    for (int i = 0; i < n; ++i) {
      sort(edges[i].begin(), edges[i].end());
    }

    max_dist = 0;
    for (int i = 0; i < n; ++i) {
      memset(used, false, sizeof(used));
      dfs(i, 0);
    }

    printf("%d\n", max_dist);
    for (int i = 0; i < (int)answer_path.size(); ++i) {
      if (i > 0)
        putchar(' ');
      printf("%d", answer_path[i] + 1);
    }
    puts("");
  }
}