#include <iostream>
using namespace std;

const int MAX=51;
int A[MAX][MAX], oldA[MAX][MAX];

struct edge
{
  int A,B;
};

edge Edges[MAX];
int Best, BestTwo, BestThree;
int BestPR[MAX];
int BestOneTown;
int d[MAX], pr[MAX];
int n, m;

void PrintOptimal(){
  cout<<" best distance form 0 to 1: "<<BestThree<<endl;
  cout<<"pr: ";
  for(int i=0;i<=m;i++) cout<< pr[i]<<' ';
  cout<<endl;
  cout<<"d: ";
  for(int i=0;i<=m;i++) cout<< d[i]<<' ';
  cout<<endl;
}

void PrintStuff(){
  //print edges
  cout<<"Edges:"<<endl;
  for(int i=0;i<n;i++)
    cout<<Edges[i].A<<','<<Edges[i].B<<endl;
  cout<<"Grid: m ="<<m<<endl;
  for(int i=0;i<m+1;i++){
    for(int j=0;j<m+1;j++)
      cout<<oldA[i][j]<<' ';
    cout<<endl;
  }
}

void initGrid(int n){
  //intitalize oldA - before getting edges
  for(int i=0;i<n+1;i++)
    for(int j=0;j<n+1;j++)
     oldA[i][j]=-1;           // = no edge
}

void copyGrid(int m){
  //copy oldA[][] to A[][]
  for(int i=0;i<m+1;i++)
   for(int j=0;j<m+1;j++)
    A[i][j] = oldA[i][j];
}

int biggest(int a, int b, int c){
  if(a>=b && a>=c) return a;
  if(b>=a && b>= c) return b;
  return c;
}
 
void GetEdges(int n){
  //get n edges - put in Edges[] and oldA[][]
  int a, b, w;

  m=1;
  for(int i=0;i<n;i++){
    cin>> a >> b >> w;
    Edges[i].A = a; Edges[i].B = b;
    oldA[a][b] = oldA[b][a] = w;
    m = biggest(m, a, b);            //to get # of nodes
  }
}

//find # of legs in path from 0 to 1 (we know such a path exists
int Legs(int *A){
  int L = 0, pos=1;
  while(pos>0){
    pos = A[pos];
    L++;
  }
  return L;
}

// shortest Path stuff

void Relax(int u, int v){  // used by Bellman-Ford, only call if (u,v) an edge
  if( (d[v]==1000000 && d[u]<1000000) || d[v] > d[u] + A[u][v]){
    d[v] = d[u] + A[u][v];
    pr[v] = u;
  }
}

void B_F(){  // Bellman-Ford to find SP from 0 to 1
  int a, b;
  //intialize d[] and pr[]
  for(int i=0;i<=m;i++){
   d[i] = 1000000;
   pr[i] = -1;
  }
  d[0] = 0; 

  for(int i=0;i<=m;i++){
    for(int e=0;e<n;e++){
      Relax(Edges[e].B, Edges[e].A);
      Relax(Edges[e].A, Edges[e].B);
    }
  }
  for(int e=0;e<n;e++){
    a = Edges[e].A; b = Edges[e].B;
    if(d[b] > d[a] + A[a][b]){
      cout<<" error in Bellman Ford: not connected"<<endl;
      exit(0);
    }
  }

  //got the shortest path - update Best (don't allow 2 path: d[1]=0)
  if(d[1]>0 && d[1] < BestThree){
    BestThree = d[1];
    //copy pr[] to BestPR[]
    for(int i=0;i<m+1;i++) BestPR[i] = pr[i];
  }
  else if(d[1]>0 && d[1] == BestThree){
    //see if fewer legs
    if(Legs(pr) < Legs(BestPR)){
      BestThree = d[1];
      for(int i=0;i<m+1;i++) BestPR[i] = pr[i];
    }
    else if(Legs(pr) == Legs(BestPR)){
      //see if lex sooner
      //first we build the paths
      int p1[m+1], p2[m+1];
      int k=1, pos;
      p1[0] = 1;
      pos = 1; 
      while(pos>0){
        pos = pr[pos];
         p1[k++] = pos;
      }
      k=1;
      p2[0] = 1;
      pos = 1; 
      while(pos>0){
        pos = BestPR[pos];
         p2[k++] = pos;
      }

      //now see if pr is lex before BestPR (possible they are ==, in which case, no update)
      //find 0 in the paths and work backwards
      k=0; while(p1[k]>0) k++;
      while(p1[k]==p2[k] && p1[k]!=1) k--;
      if(p1[k]<p2[k])  //update, BestThree is the same
        for(int i=0;i<m+1;i++) BestPR[i] = pr[i];
    }
  }
}

void PrintPath(int i){
  //recursive print from 0 to 1 (first call with i=1)
  if (i==0) cout<<i<<' ';
  else {
    PrintPath(BestPR[i]);
    cout<<i<<' ';
  }
}

int main(){
  int a,b,Cost;

  cin>>n;
  while(n>0){
    initGrid(n);
    GetEdges(n);

    //find best pth with >2 legs - state pays for 2
    BestThree = 1000000;
     for(int e1=0;e1<n-1;e1++)
       for(int e2=e1;e2<n;e2++){ 
         //make edges e1 and e2 =0 and find shortest path for all e1 e2
         copyGrid(m);
         a = Edges[e1].A; b = Edges[e1].B;
         A[a][b]=A[b][a]=0;
         a = Edges[e2].A; b = Edges[e2].B;
         A[a][b]=A[b][a]=0;
         B_F();
       }

/*
cout<<"BestThree="<<BestThree<<endl;
PrintPath(1);cout<<endl;
PrintStuff();
*/
    //got the best path with >2 legs. now try 2 legs
    BestTwo = 1000000;
    copyGrid(m);
    //try all intermediate nodes
    for(int k=2;k<=m;k++){
      if(A[0][k]>-1 && A[k][1]>-1){
        Cost = A[0][k];
        if(A[k][1]<Cost) Cost = A[k][1];
        //update BestTwo
        if(Cost < BestTwo){
         BestTwo = Cost;
         BestOneTown = k;
        }
      }
    }
//cout<<"BestTwo="<<BestTwo<<endl;

   //got 2 step and > 2 step, now look at direct 
   if(A[0][1]>-1) Best=A[0][1];
    else Best = 1000000;
//cout<<"Best="<<Best<<endl;

   //see which is best
   if(Best<=BestTwo && Best<=BestThree)
    cout<<"0 1 "<<Best<<endl;
   
   else if (BestTwo<=BestThree && BestTwo<=Best)
     cout<<"0 "<< BestOneTown<< " 1 "<<BestTwo<<endl;
   else{
     PrintPath(1);
     cout<<BestThree<<endl;
   }

    cin>>n;
  }
  
  return 0;
}