#include<stdio.h>
#include<algorithm>
using namespace std;
int p[30];
int q[30];
int r[30];
int tmp[30];
int ans[30];
int m;
int used[30];
int ret;
void dfs(int a,int b,int c){
	if(ret<b){
		ret=b;
		for(int j=0;j<30;j++)ans[j]=tmp[j];
	}else if(ret==b){
		bool ok=false;
		for(int j=0;j<30;j++){
			if(!~ans[j]||ans[j]<tmp[j]){ok=false;break;}
			if(!~tmp[j]||ans[j]>tmp[j]){ok=true;break;}
		}
		if(ok)for(int j=0;j<30;j++)ans[j]=tmp[j];
	}
	for(int i=0;i<m;i++){
		if(used[i])continue;
		if(p[i]==a){
			used[i]=1;
			tmp[c+1]=q[i];
			dfs(q[i],b+r[i],c+1);
			used[i]=0;
		}else if(q[i]==a){
			used[i]=1;
			tmp[c+1]=p[i];
			dfs(p[i],b+r[i],c+1);
			used[i]=0;
		}
	}
}
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b),a){
		m=b;
		for(int i=0;i<b;i++){
			scanf("%d%d%d",p+i,q+i,r+i);
			p[i]--;q[i]--;
		}
		ret=0;
		for(int i=0;i<a;i++){
			for(int j=0;j<30;j++)used[j]=0;
			for(int j=0;j<30;j++)tmp[j]=-1;
			tmp[0]=i;
			dfs(i,0,0);
		}
		printf("%d\n",ret);
		for(int i=0;~ans[i];i++){
			if(i)printf(" ");
			printf("%d",ans[i]+1);
		}printf("\n");
	}
}