#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define INF 1000000
#define MAXN 32
int N;
int matrix[MAXN][MAXN];
int dist[MAXN];
int path[MAXN];
int s[MAXN];
void dijkstra(int u){
/* init */
int i, j, k;
int min;
int v;
int tmp;
for(i =0; i < N; i++){
s[i]=0;
dist[i]= matrix[u][i];
if(dist[i]!= INF && i != u){
path[i]= u;
}
else{
path[i]=-1;
}
}
s[u]=1;
dist[u]=0;
for(i =1; i < N; i++){
min = INF;
for(j =0; j < N; j++){
if(!s[j]&& dist[j]< min){
min = dist[j];
v = j;
}
}
s[v]=1;
for(k =0; k < N; k++){
if(s[k]){
continue;
}
tmp = dist[v]+ matrix[v][k];
if(dist[k]> tmp){
dist[k]= tmp;
path[k]= v;
}
}
}
}
void print_path(int u){
int rev[MAXN];
int count =0;
int i;
int v;
memset(rev,0,sizeof(rev));
rev[count++]= u;
v = path[u];
while(v !=-1){
rev[count ++]= v;
v = path[v];
}
for(i = count -1; i >=0; i--){
if(i == count -1){
printf("%d", rev[i]);
}
else{
printf("->%d", rev[i]);
}
}
}
int main(){
int i, j;
int u, v, w;
scanf("%d",&N);
memset(matrix,0,sizeof(matrix));
while(1){
scanf("%d%d%d",&u,&v,&w);
if(u ==-1&& v ==-1&& w ==-1){
break;
}
matrix[u][v]= w;
}
for(i =0; i < N; i++){
for(j =0; j < N; j++){
if(i == j){
matrix[i][j]=0;
}
elseif(matrix[i][j]==0){
matrix[i][j]= INF;
}
}
}
dijkstra(0);
for(i =1; i < N; i++){
printf("%d-->%d:%d\t",0, i, dist[i]);
print_path(i);
printf("\n");
}
return0;
}