[html]
#include<stdio.h> 
#include<string.h> 
#include<iostream> 
#include<queue> 
using namespace std ; 
const int INF = 1000000 ; 
const int maxn = 10 ; 
struct ArcNode 
{ 
    int to ; 
    int weight ; 
    ArcNode *next ; 
}; 
queue<int> Q ; 
int n ; 
ArcNode *List[ maxn ] ; 
int inq[ maxn ]  ; 
int dist[ maxn ] , path[ maxn ] ; 
void SPFA( int src ) 
{ 
    int i , u ; 
    ArcNode * temp ; 
    for( i = 0 ; i < n ; i++ ) 
    { 
        dist[ i ] = INF ; 
        path[ i ] = src ; 
        inq[ i ] = 0 ; 
    } 
    dist[ src ] = 0 ; 
    path[ src ] = src ; 
    inq[ src ]++ ; 
    Q.push( src ) ; 
    while( !Q.empty() ) 
    { 
        u = Q.front() ; 
        Q.pop() ; 
        inq[ u ]-- ; 
        temp = List[ u ] ; 
        while( temp != NULL ) 
        { 
            int v= temp-> to ; 
            if( dist[ v ] > dist[ u ] + temp->weight ) 
            { 
                dist[ v ] = dist[ u ] + temp -> weight ; 
                path[ v ] = u ; 
                if( !inq[ v ] ) 
                { 
                    Q.push( v ) ; 
                    inq[ v ]++ ; 
                } 
            } 
            temp = temp -> next ; 
        } 
    } 
} 
 
int main() 
{ 
    int  i , j ; 
    int u , v , w ; 
    scanf( "%d" , &n ); 
    memset( List , 0 , sizeof( List ) ) ; 
    ArcNode *temp ; 
    while( 1 )  
    { 
        scanf( "%d%d%d" ,&u , &v , &w ) ; 
        if( u == -1 && v == -1 && w == -1 ) 
            break ; 
        temp = new ArcNode ; 
        temp -> to = v ; 
        temp -> weight = w; 
        temp -> next = NULL ; 
        if( List[ u ] == NULL ) 
            List[ u ] = temp ; 
        else 
        { 
            temp -> next = List[ u ] ; 
            List[ u ] = temp ; 
        } 
    } 
    SPFA( 0 ) ; 
    for( j = 0 ; j < n ; j++ ) 
    { 
        temp = List[ j ] ; 
        while( temp != NULL ) 
        { 
            List[ j ] = temp -> next ; 
            delete temp ; 
            temp = List[ j ] ; 
        } 
    } 
    int shortest[ maxn ] ; 
    for( i = 1 ; i < n ; i++ ) 
    { 
        printf( "%d\t" , dist[ i ] ) ; 
        memset( shortest , 0 , sizeof( shortest ) ) ; 
        int k = 0 ; 
        shortest[ k ] = i ; 
        while( path[ shortest[ k ] ] != 0 ) 
        { 
            k++ ; 
            shortest[ k ] = path[ shortest[ k - 1 ] ] ; 
        } 
        k++ ; 
        shortest[ k ] = 0 ; 
        for( j = k ; j > 0 ; j-- ) 
            printf( "%d->" , shortest[ j ] ) ; 
        printf( "%d\n" , shortest[ 0 ] ) ; 
    } 
} 

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<queue>
using namespace std ;
const int INF = 1000000 ;
const int maxn = 10 ;
struct ArcNode
{
 int to ;
 int weight ;
 ArcNode *next ;
};
queue<int> Q ;
int n ;
ArcNode *List[ maxn ] ;
int inq[ maxn ]  ;
int dist[ maxn ] , path[ maxn ] ;
void SPFA( int src )
{
 int i , u ;
 ArcNode * temp ;
 for( i = 0 ; i < n ; i++ )
 {
  dist[ i ] = INF ;
  path[ i ] = src ;
  inq[ i ] = 0 ;
 }
 dist[ src ] = 0 ;
 path[ src ] = src ;
 inq[ src ]++ ;
 Q.push( src ) ;
 while( !Q.empty() )
 {
  u = Q.front() ;
  Q.pop() ;
  inq[ u ]-- ;
  temp = List[ u ] ;
  while( temp != NULL )
  {
   int v= temp-> to ;
   if( dist[ v ] > dist[ u ] + temp->weight )
   {
    dist[ v ] = dist[ u ] + temp -> weight ;
    path[ v ] = u ;
    if( !inq[ v ] )
    {
     Q.push( v ) ;
     inq[ v ]++ ;
    }
   }
   temp = temp -> next ;
  }
 }
}

int main()
{
 int  i , j ;
 int u , v , w ;
 scanf( "%d" , &n );
 memset( List , 0 , sizeof( List ) ) ;
 ArcNode *temp ;
 while( 1 )
 {
  scanf( "%d%d%d" ,&u , &v , &w ) ;
  if( u == -1 && v == -1 && w == -1 )
   break ;
  temp = new ArcNode ;
  temp -> to = v ;
  temp -> weight = w;
  temp -> next = NULL ;
  if( List[ u ] == NULL )
   List[ u ] = temp ;
  else
  {
   temp -> next = List[ u ] ;
   List[ u ] = temp ;
  }
 }
 SPFA( 0 ) ;
 for( j = 0 ; j < n ; j++ )
 {
  temp = List[ j ] ;
  while( temp != NULL )
  {
   List[ j ] = temp -> next ;
   delete temp ;
   temp = List[ j ] ;
  }
 }
 int shortest[ maxn ] ;
 for( i = 1 ; i < n ; i++ )
 {
  printf( "%d\t" , dist[ i ] ) ;
  memset( shortest , 0 , sizeof( shortest ) ) ;
  int k = 0 ;
  shortest[ k ] = i ;
  while( path[ shortest[ k ] ] != 0 )
  {
   k++ ;
   shortest[ k ] = path[ shortest[ k - 1 ] ] ;
  }
  k++ ;
  shortest[ k ] = 0 ;
  for( j = k ; j > 0 ; j-- )
   printf( "%d->" , shortest[ j ] ) ;
  printf( "%d\n" , shortest[ 0 ] ) ;
 }
}[html]
/* 

/*[html]
7 
0 1 6 
0 2 5 
0 3 5 
1 4 -1 
2 1 -2 
2 4 1 
3 2 -2 
3 5 -1 
4 6 3 
5 6 3 
-1 -1 -1 
1       0->3->2->1 
3       0->3->2 
5       0->3 
0       0->3->2->1->4 
4       0->3->5 
3       0->3->2->1->4->6 

7
0 1 6
0 2 5
0 3 5
1 4 -1
2 1 -2
2 4 1
3 2 -2
3 5 -1
4 6 3
5 6 3
-1 -1 -1
1       0->3->2->1
3       0->3->2
5       0->3
0       0->3->2->1->4
4       0->3->5
3       0->3->2->1->4->6
[html]
*/ 

*/