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

int ns,nl;
struct edge{
	int to,cost,used,rev;
	edge(){}
	edge(int tt,int cc,int revv){
		to=tt;
		cost=cc;
		used=0;
		rev=revv;
	}
};
typedef pair<int,int> P;
vector<edge> G[21];
vector<int> res;
vector<int> pass;
int cost,rescost;

bool passmax(vector<int> &a,vector<int> &b){
	if(a.size()>b.size())return true;
	if(b.size()>a.size())return false;
	for(int i=0;i<min(a.size(),b.size());i++){
		if(a[i]>b[i])return false;
		if(b[i]<a[i])return true;
	}
	return true;
}

void dfs(int v){
	if(cost>rescost ||(cost==rescost && passmax(pass,res))){
		rescost=cost;
		res=pass;
	}
	for(int i=0;i<G[v].size();i++){
		edge &e=G[v][i];
		if(e.used==0){
			cost+=e.cost;
			e.used++;
			G[e.to][e.rev].used++;
			pass.push_back(e.to);
			dfs(e.to);
			pass.pop_back();
			cost-=e.cost;
			e.used--;
			G[e.to][e.rev].used--;
		}
	}
}

void check(){
	res.clear();
	rescost=0;
	for(int i=1;i<=ns;i++){
		cost=0;
		pass.push_back(i);
		dfs(i);
		pass.pop_back();
	}
}
int main(void){
	while(1){
		scanf("%d %d",&ns,&nl);
		if(ns+nl==0)break;
		for(int i=0;i<=ns;i++){
			G[i].clear();
		}
		for(int i=0;i<nl;i++){
			int a,b,c;
			scanf("%d %d %d",&a,&b,&c);
			G[a].push_back(edge(b,c,G[b].size()));
			G[b].push_back(edge(a,c,G[a].size()-1));
		}
		check();
		printf("%d\n",rescost);
		for(int i=0;i<res.size();i++){
			printf("%d%c",res[i],i==res.size()-1?'\n':' ');
		}
	}
	return 0;
}