// travelling salesman for COP4020
#include <iostream.h>

#define max_nodes 10

int edges[max_nodes][max_nodes]={0};

void read_edges() {
int node1, node2, cost;
while (cin) {
  cin >> node1 >> node2 >> cost;
  edges[node1][node2]=edges[node2][node1]=cost;
  }
}

void print_edges(int n_nodes) {
int r, c;
for (r=0;r<n_nodes;r++){
  for (c=0;c<n_nodes;c++) cout << edges[r][c] << " ";
  cout << endl;
  }
}

int best_cost=9999;

int path[max_nodes], p_len=0;

int contains(int node) {
int i;
for (i=0;i<p_len;i++)
  if (path[i]==node) return 1;
return 0;
}

void print_path() {
int i; for (i=0;i<p_len-1;i++) cout << path[i] << "->";
cout << path[i];
}

void push (int n) {
path[p_len++]=n;
//cout <<"push:"; print_path(); cout << endl;
}

void pop()
{ path[p_len-- - 1]=0;
//cout <<"pop:"; print_path(); cout << endl;
}

int done(int node, int n)
{ return node==path[0] && p_len==n;}

void tryit(int node, int cost, int n_nodes) {
if (done(node, n_nodes)){
    print_path();
    cout << "->" << node << " " << cost << endl;
    return;
    }
if (contains(node)) return;
push(node);
int i;
for (i=0;i<n_nodes; i++){
   if (edges[i][node]==0) continue;
   tryit(i,cost+edges[node][i], n_nodes);
   }
pop();
}

main() {
int n_nodes=0;

cin >> n_nodes;
read_edges();
tryit(0,0,n_nodes);
print_path();

return 0;
}