#include <iostream>
using namespace std;

const int MAX = 1000;
const int INF = 100000000;

int edgeCost[MAX];
int nedges;

class Edge
{
public:
	int w;
	int icost;
	Edge *next;

	Edge(int ww, int cc, Edge* n) : w(ww), icost(cc), next(n)
	{}

	int cost() {
		return edgeCost[icost];
	}
};

class Vertex
{
public:
	Edge *adj;
	int prev, cost;
	int numEdges;
	bool visited;

	Vertex() : adj(0), prev(-1), cost(INF) {}

	void init()
	{
		prev = -1;
		cost = INF;
		numEdges = 0;
		visited = false;
	}

	void addEdge(int w, int cost)
	{
		if (adj == 0 || w < adj->w) {
			adj = new Edge(w, cost, adj);
			return;
		}
		Edge *p = adj;
		while (p->next != 0 && w > p->w)
			p = p->next;
		p->next = new Edge(w, cost, p->next);
	}
} cities[MAX+1];

int bestCost;
int bestPath[MAX+1];
int bestPathLength;


int nextMinVertex(int n)
{
	int ans = -1;
	int cost = INF;
	for(int i=1; i<n; i++) {
		if (!cities[i].visited && cities[i].cost < cost) {
			cost = cities[i].cost;
			ans = i;
		}
	}
	return ans;
}

bool betterPath(int e)
{
	if (cities[e].numEdges < bestPathLength)
		return true;
	else if (cities[e].numEdges > bestPathLength)
		return false;
	else {
		int path[MAX];
		int v=e;
		for(int i=cities[e].numEdges; i>=0; i--) {
			path[i] = v;
			v = cities[v].prev;
		}
		for(int i=0; i<cities[e].numEdges; i++)
			if (path[i] < bestPath[i])
				return true;
			else if (path[i] > bestPath[i])
				return false;
		return false;
	}
}

void dijkstra(int s, int e, int n)
{
	for(int i=0; i<n; i++)
		cities[i].init();
	cities[0].cost = 0;
	int v=0;
	while (true) {
////cout << "visiting vertex " << v << endl;
		cities[v].visited = true;
		if (v == -1) {
			cout << "ERROR: can't reach 1" << endl;
			exit(-1);
		}
		if (v == e)
			break;
		for(Edge *e = cities[v].adj; e!=0; e=e->next) {
			int w = e->w;
			if (cities[v].cost + e->cost() < cities[w].cost) {
//cout << "  updating vertex " << w << " with new cost " << cities[v].cost +e->cost() << endl;;
				cities[w].cost = cities[v].cost + e->cost();
				cities[w].prev = v;
				cities[w].numEdges = cities[v].numEdges+1;
			}
		}
		v = nextMinVertex(n);
	}
	if (cities[e].cost == 0)
		return;
	if (cities[e].cost < bestCost || (cities[e].cost == bestCost && betterPath(e))) {
		bestCost = cities[e].cost;
		v = e;
		for(int i=cities[e].numEdges; i>=0; i--) {
			bestPath[i] = v;
			v = cities[v].prev;
		}
		bestPathLength = cities[e].numEdges;
	}
}

int main()
{
	int n;
	cin >> n;
	while (n > 0) {
		for(int i=0; i<=n; i++) {
			cities[i].adj = 0;
		}
		nedges=0;
		int ncities = 0;
		for(int i=0; i<n; i++) {
			int s, e, cost;
			cin >> s >> e >> cost;
			edgeCost[nedges] = cost;
			cities[s].addEdge(e, nedges);
			cities[e].addEdge(s, nedges);
			nedges++;
			if (s > ncities)
				ncities = s;
			if (e > ncities)
				ncities = e;
		}
		ncities++;

		bestCost = INF;
		dijkstra(0, 1, ncities);
		for(int i=0; i<nedges; i++) {
			int icost = edgeCost[i];
			edgeCost[i]= 0;
			dijkstra(0, 1, ncities);
			for(int j=i+1; j<nedges; j++) {
				int jcost = edgeCost[j];
				edgeCost[j]= 0;
				dijkstra(0, 1, ncities);
				edgeCost[j]= jcost;
			}
			edgeCost[i]= icost;
		}
		for(int i=0; i<=bestPathLength; i++)
			cout << bestPath[i] << ' ';
		cout << bestCost << endl;
					
		cin >> n;
	}
}