#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
const int mx=11;
const int mxe=21;
const int mxb=(1<<mxe);
vector<int>g[mx];
vector<int>w[mx];
vector<int>e[mx];
int f[mx][mxb];
int nxt[mx][mxb];
int main(){
   int n,m,u,v,wuv;
   while(scanf("%d %d",&n,&m),n!=0 && m!=0){
      for(int i=0;i<n;i++){
         g[i].clear();
         w[i].clear();
         e[i].clear();
      }
      for(int i=0;i<m;i++){
         scanf("%d %d %d",&u,&v,&wuv);
         u--,v--;
         g[u].push_back(v);
         g[v].push_back(u);
         w[u].push_back(wuv);
         w[v].push_back(wuv);      
         e[u].push_back(i);
         e[v].push_back(i);
      }
      for(int b=(1<<m)-1;b>=0;b--){
         for(u=0;u<n;u++){
            int &fu=f[u][b];
            int &nu=nxt[u][b];
            fu=0,nu=-1;
            for(int i=0;i<int(g[u].size());i++){
               v=g[u][i];     
               int euv=e[u][i];
               if(b&(1<<euv))continue;
               int bet=w[u][i]+f[v][b^(1<<euv)];
               if(bet>fu)fu=bet,nu=i;
               else if(bet==fu && v<g[u][nu])nu=i;
            }
         }
      }
      int x=0;
      for(u=0;u<n;u++)
         if(f[u][0]>f[x][0])
            x=u;
      u=x;
      printf("%d\n",f[u][0]);
      int b=0,cnt=0;
      while(true){
         if(cnt!=0)printf(" ");
         printf("%d",u+1);
         int euv=nxt[u][b];
         if(euv==-1)break;
         v=g[u][euv];
         b^=(1<<e[u][euv]);
         u=v;
         cnt++;
      }
      printf("\n");
   }
   return 0;
}