/*
 * Solution to "You'll Be Working on the Railroad"
 */
import java.util.*;

class Pair {
   public int n, c;
   public Pair(int n, int c) {
     this.n = n; this.c = c;
   }
}

class Node {
  public int id;
  public ArrayList<Edge> nbr;
  public Node(int id) {
    this.id = id;
    nbr = new ArrayList<Edge>();
  }
  public void add(Edge e) {
    nbr.add(e);
  }
}

class Edge implements Comparable<Edge>{
  public int s,e,c;
  public Edge(int s, int e, int c) {
    this.s = s; this.e = e; this.c = c;
  }
  
  public int compareTo(Edge other) {
    if (s < other.s) return -1;
    else if (s == other.s && e < other.e) return -1;
    else return 1;
  }
}

public class Railroad {
  public static int n,m;
  public static Edge edge[];
  public static Node graph[];
  public static Scanner in;
  public static int minCost, minSegs;
  public static ArrayList<Integer> solution;
  public static int dist[], length[], prev[];

  public static void main(String[] args) {
    in = new Scanner(System.in);
    while ((n = in.nextInt()) != 0) {
      edge = new Edge[2*n];
      int j = 0;
      for (int i = 0; i < n; i++) {
        int s = in.nextInt();
        int e = in.nextInt();
        int c = in.nextInt();
        edge[j] = new Edge(s,e,c);
        edge[j+1] = new Edge(e,s,c);
        j += 2;
      }
      Arrays.sort(edge);
      m = edge[2*n-1].s;
      graph = new Node[m+1];
      for (int i = 0; i <= m; i++)
        graph[i] = new Node(i);
      for (int i = 0; i < 2*n; i++) {
        Edge ed = edge[i];
        int s = ed.s;
        graph[s].add(ed);
      }
     
      minCost = Integer.MAX_VALUE;
      minSegs = Integer.MAX_VALUE;
      solution = new ArrayList<Integer>();
      solution.add(0);
      solve();
      for (int i = 0; i < solution.size(); i++) {
        System.out.print(solution.get(i)+" ");
      }
      System.out.println(minCost);
    }
  }

  public static void solve() {
    // first, see if there's an edge from 0 to 1:
    Edge ed1 = graph[0].nbr.get(0);
    if (ed1.e == 1) {
      minCost = ed1.c;
      minSegs = 1;
      solution.add(1);
    }

    // Now try setting all possible edges to 0 and see if there
    // is a solution with just two edges:
    for (int i = 0; i < 2*n; i++) {
      Edge ed = edge[i];
      Edge ed2 = null;
      if (ed.s > ed.e) 
        continue;
      int temp = ed.c;
      for (int k = i+1; k < 2*n; k++) {
        ed2 = edge[k];
        if (ed2.s == ed.e && ed2.e == ed.s) {
          break;
        }
      }
      ed.c = 0;
      ed2.c = 0;
      // Now for each neighbor of 0, see if that neighbor connects to 1:
      for (Edge nb : graph[0].nbr) {
        int next = nb.e;
        for (Edge nb2 : graph[next].nbr) {
          if (nb2.e == 1) {
            int cost = nb.c + nb2.c;
            if (cost == minCost && minSegs == 2) {
              ArrayList<Integer> tentative  = new ArrayList<Integer>();
              tentative.add(0);
              tentative.add(nb.e);
              tentative.add(1);
              if (lessThan(tentative,solution)) {
                solution = tentative;
              }
            }
            else if (cost < minCost) {
              minCost = cost;
              minSegs = 2;
              solution.clear();
              solution.add(0);
              solution.add(nb.e);
              solution.add(1);
            }
          }
        }
      }
      ed.c = temp;
      ed2.c = temp;
    }

    // Finally, we look for pairs of edges that can be set to 0, and we
    // invoke Dijkstra's algorithm for each such pair. We must
    // make sure that the solution involves a minimum of three edges
    for (int i = 0; i < 2*n-2; i++) {
      Edge ed = edge[i];
      int e1rev = 0,e2rev = 0;
      if (ed.s > ed.e) continue;
      for (int j = i+1; j < 2*n-1; j++) {
        Edge ed2 = edge[j];
        if (ed2.e == ed.s && ed2.s == ed.e) {
          continue;
        }
        else if (ed2.s > ed2.e) continue;
// we've found out ed2; now we have to find their matching "reverse" edges:

        for (int k = i+1; k < 2*n; k++) {
          Edge temp = edge[k];
          if (temp.e == ed.s && temp.s == ed.e) {
            e1rev = k;
            break;
          }
        }

        for (int k = j+1; k < 2*n; k++) {
          Edge temp = edge[k];
          if (temp.e == ed2.s && temp.s == ed2.e) {
            e2rev = k;
            break;
          }
        }
        int temp1 = ed.c;
        int temp2 = ed2.c;
        ed.c = 0;
        ed2.c = 0;
        edge[e1rev].c = 0;
        edge[e2rev].c = 0;
//System.out.println("Setting edge from " + ed.s + " to " + ed.e + " to 0");
//System.out.println("Setting edge from " + ed2.s + " to " + ed2.e + " to 0");
        dijkstra();
        int cost = dist[1];        
        if (cost == minCost && minSegs == length[1]) {
          ArrayList<Integer> tentative  = new ArrayList<Integer>();
          int a = 1;
          while (a > -1) {
            tentative.add(0,a);
            a = prev[a];
          }
          if (lessThan(tentative,solution)) {
            solution = tentative;
          }
        }
        else if (cost < minCost && length[1] >= 3) {
          minCost = cost;
          minSegs = length[1];
          solution.clear();
          int a = 1;
          while (a > -1) {
            solution.add(0,a);
            a = prev[a];
          }
        }
//System.out.println("answer = "+answer);
//System.out.print("path = ");
//int a = 1;
//while (a > -1) {
//   System.out.print(a+" ");
//   a = prev[a];
//}
//System.out.println();


        ed.c = temp1;
        ed2.c = temp2;
        edge[e1rev].c = temp1;
        edge[e2rev].c = temp2;
      }
    }
    

  }

  public static void dijkstra() {
    dist = new int[m+1];
    for (int i = 0; i <= m; i++)
      dist[i] = Integer.MAX_VALUE;
    prev = new int[m+1];
    for (int i = 0; i <= m; i++)
      prev[i] = -1;
    boolean visited[] = new boolean[m+1];
    for (int i = 0; i <= m; i++)
      visited[i] = false;
    length = new int[m+1];
    for (int i = 0; i <= m; i++)
      length[i] = -1;
    dist[0] = 0;
    length[0] = 0;
    for (int i = 1; i <= m; i++) {
      int m = min(dist,visited);
      visited[m] = true;
      ArrayList<Edge> nbr = graph[m].nbr;
      for (Edge e : nbr) {
        int k = e.e;
        if (dist[m] + e.c < dist[k]) {
          dist[k] = dist[m] + e.c;
          prev[k] = m;
          length[k] = length[prev[k]]+1;
        }
      }
    }
//    System.out.println("Distance from 0:");
//    for (int i = 0; i <= m; i++) {
//      System.out.println(i+": "+dist[i]);
//    }
  }

  public static int min(int dist[], boolean visited[]) {
    int min = Integer.MAX_VALUE;
    int result = 0;
    for (int i = 0; i < dist.length; i++) {
      if (!visited[i] && dist[i] < min) {
        result = i;
        min = dist[i];
      }
    }
    return result;
  }

  public static boolean lessThan(ArrayList<Integer> i, ArrayList<Integer> j) {
    if (i.size() < j.size()) return true;
    int k = 0;
    while (k < i.size()-1 && i.get(k) == j.get(k)) k++;
    return i.get(k) < j.get(k);
  }
}