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

int n,m;
int dist[10][10];
bool used[10][10];
int max_len, curr_len;
vector<int> max_nodes, curr_nodes;

void dfs(int v){
    curr_nodes.push_back(v);
    bool end = true;
    for(int i=0; i<n; i++){
        if(dist[v][i]==0 or used[v][i]) continue;
        end = false;
        used[v][i] = used[i][v] = true;
        curr_len += dist[v][i];
        dfs(i);
        curr_len -= dist[v][i];
        used[v][i] = used[i][v] = false;
    }
    if(end){
        if(curr_len > max_len){
            max_len = curr_len;
            max_nodes = curr_nodes;
        }
    }
    curr_nodes.pop_back();
}

int main(){
    while(1){
        cin >> n >> m;
        if(n == 0) break;

        memset(dist, 0, sizeof(dist));
        max_len = 0;
        max_nodes.clear();
        for(int i=0; i<m; i++){
            int a,b,c;
            cin >> a >> b >> c;
            a--; b--;
            dist[a][b] = dist[b][a] = c;
        }
        for(int i=0; i<n; i++){
            dfs(i);
        }
        cout << max_len << endl;
        for(int i=0; i<(int)max_nodes.size()-1; i++){
            cout << max_nodes[i]+1 << " ";
        }
        cout << max_nodes.back()+1 << endl;
    }
    return 0;
}
