#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int ns,nl,cnt;
int vec[12][12];
bool used[12][12];
vector<int> dis;
const int INF = 1<<30;

void permutation(int s,int cost,vector<int> P){
  bool fin = true;
  
  for(int i=1;i<=ns;i++){
    if(!used[s][i] && vec[s][i] != INF && i!=s){
      fin = false;
      P.push_back(i);
      used[s][i] = used[i][s] = true;
      permutation(i,cost+vec[s][i],P);
      used[s][i] = used[i][s] = false;
      P.pop_back();
    }
  }
  
  if(fin){
    if(cnt <= cost){
      if(cnt == cost){
	bool AorB = false;//true -> dis, false -> P
	for(int i=0;i<min(dis.size(),P.size());i++){
	  if(dis[i] > P[i]){
	    AorB = false;
	    break;
	  }
	  else if(dis[i] < P[i]){
	    AorB = true;
	    break;
	  }
	}
	if(!AorB){
	  dis.clear();
	  copy(P.begin(),P.end(),back_inserter(dis));
	}
      }
      else if(cnt < cost){
	dis.clear();
	copy(P.begin(),P.end(),back_inserter(dis));
      }   
      cnt = cost;
    }
  }

}

int main(){
  int s1,s2,d;
 
  while(true){
    cin >> ns >> nl;
    if(ns+nl == 0)break;
    dis.clear();
    dis.push_back(9999999);
    for(int j=0;j<12;j++)for(int i=0;i<12;i++){
	vec[i][j]=INF;    
	used[j][i] = false;
      }
    cnt = 0;

    for(int i=0;i<nl;i++){
      cin >> s1 >> s2 >> d;
      vec[s1][s2] = vec[s2][s1] = d;
    }

    vector<int> pos;
    for(int i=1;i<=ns;i++){
      pos.push_back(i);
      
      permutation(i,0,pos);
      for(int k=0;k<12;k++)for(int j=0;j<12;j++)used[k][j] = false;
      pos.pop_back();
    }
    cout << cnt << endl;
    for(int i=0;i<dis.size();i++){
      cout << dis[i];
      if(i == dis.size()-1)cout<< endl;
      else cout << " ";
    }
  }
  return 0;
}