#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;

struct Info{
	Info(int arg_to,int arg_dist,int arg_id){
		to = arg_to;
		dist = arg_dist;
		id = arg_id;
	}

	int to,dist,id;
};

struct Data{
	bool operator<(const struct Data &arg) const{
			return sum_dist > arg.sum_dist;
	};
	void set(int arg_station,int arg_state,int arg_sum_dist){
		station = arg_station;
		state = arg_state;
		sum_dist = arg_sum_dist;
	}

	int station,state,sum_dist;
	vector<int> History;
};

int N,M;
int POW[21],max_dist[1048576];

void func(){

	vector<Info> V[N];

	int from,to,dist;

	for(int loop = 0; loop < M; loop++){
		scanf("%d %d %d",&from,&to,&dist);
		from--;
		to--;
		V[from].push_back(Info(to,dist,loop));
		V[to].push_back(Info(from,dist,loop));
	}

	for(int i = 0; i < POW[M]; i++){
		max_dist[i] = 0;
	}

	priority_queue<Data> Q;
	vector<int> ANS;

	int maximum = 0;

	for(int i = 0; i < N; i++){
		Data first;
		first.set(i,0,0);
		first.History.push_back(i);
		Q.push(first);
	}

	int next_state,ans_index,tmp_index,smaller;

	while(!Q.empty()){

		if(maximum < Q.top().sum_dist){
			maximum = Q.top().sum_dist;
			ANS.clear();
			for(int i = 0; i < Q.top().History.size(); i++){
				ANS.push_back(Q.top().History[i]);
			}
		}else if(maximum == Q.top().sum_dist){

			ans_index = 0,tmp_index = 0;

			while(ans_index < ANS.size() && tmp_index < Q.top().History.size() && ANS[ans_index] == Q.top().History[tmp_index]){
				ans_index++;
				tmp_index++;
			}

			if(ans_index < ANS.size() && tmp_index < Q.top().History.size() && ANS[ans_index] > Q.top().History[tmp_index]){
				ANS.clear();
				for(int i = 0; i < Q.top().History.size(); i++){
					ANS.push_back(Q.top().History[i]);
				}
			}else if(ans_index < ANS.size() && tmp_index == Q.top().History.size()){
				ANS.clear();
				for(int i = 0; i < Q.top().History.size(); i++){
					ANS.push_back(Q.top().History[i]);
				}
			}
		}

		if(Q.top().sum_dist < max_dist[Q.top().state]){
			Q.pop();
		}else{

			for(int i = 0; i < V[Q.top().station].size(); i++){
				if(Q.top().state & (1 << V[Q.top().station][i].id)){
					//Do nothing
				}else{

					next_state = Q.top().state + POW[V[Q.top().station][i].id];
					if(max_dist[next_state] <= Q.top().sum_dist + V[Q.top().station][i].dist){
						max_dist[next_state] = Q.top().sum_dist + V[Q.top().station][i].dist;

						Data next;
						next.set(V[Q.top().station][i].to,next_state,max_dist[next_state]);
						for(int k = 0; k < Q.top().History.size(); k++){
							next.History.push_back(Q.top().History[k]);
						}
						next.History.push_back(V[Q.top().station][i].to);
						Q.push(next);
					}
				}
			}
			Q.pop();
		}
	}

	printf("%d\n",maximum);
	printf("%d",ANS[0]+1);
	for(int i = 1; i < ANS.size(); i++){
		printf(" %d",ANS[i]+1);
	}
	printf("\n");
}


int main(){

	for(int i = 0; i < 21; i++)POW[i] = pow(2,i);

	while(true){
		scanf("%d %d",&N,&M);
		if(N == 0 && M == 0)break;

		func();
	}

	return 0;
}

Measured memory_bytes: 3476