[html] 
#include<stdio.h> 
#include<iostream> 
#include<string.h> 
 
using namespace std ; 
const int INF = 1000000 ; 
const int maxn = 8 ;  
int n ; 
int edge[ maxn ][ maxn ] ; 
int dist[ maxn ] ; 
int path[ maxn ] ; 
void bellman( int v0 ) 
{ 
    int i , j , k , u ; 
    for( i = 0 ; i < n ; i++ ) 
    { 
        dist[ i ] = edge[ v0 ][ i ] ; 
        if( i != v0 && dist[ i ] < INF ) 
            path[ i ] = v0 ; 
        else 
            path[ i ] = -1 ; 
    } 
    for( k = 2 ; k < n ; k++ ) 
    { 
        for( u = 0 ; u < n ; u++ ) 
        { 
            if( u != v0 ) 
            { 
                for( j = 0 ;  j < n ; j++ ) 
                { 
                    if( edge[ j ][ u ] < INF && dist[ j ] + edge[ j ][ u ] < dist[ u ] ) 
                    { 
                        dist[ u ] = dist[ j ] + edge[ j ][ u ] ; 
                        path[ u ] = j ; 
                    } 
                } 
            } 
        } 
    } 
} 
 
 
int main() 
{ 
    int i , j ; 
    int u , v , w ; 
    scanf( "%d" , &n ) ; 
    while( 1 ) 
    { 
        scanf( "%d%d%d" , &u , &v , &w ) ; 
        if( u == -1 && v == -1 && w == -1 ) 
            break ; 
        edge[ u ][ v ] = w ; 
    } 
    for( i = 0 ; i < n ; i++ ) 
    { 
        for( j = 0 ; j < n ; j++ ) 
        { 
            if( i == j ) 
                edge[ i ][ j ] = 0 ; 
            else 
                if( edge[ i ][ j ] == 0 ) 
                    edge[ i ][ j ] = INF ; 
        } 
    } 
    bellman( 0 ) ; 
    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 ] ) ; 
    }    
    return 0 ; 
} 
 
<SPAN style="FONT-FAMILY: Arial, Helvetica, sans-serif">7</SPAN> 

#include<stdio.h>
#include<iostream>
#include<string.h>

using namespace std ;
const int INF = 1000000 ;
const int maxn = 8 ;
int n ;
int edge[ maxn ][ maxn ] ;
int dist[ maxn ] ;
int path[ maxn ] ;
void bellman( int v0 )
{
 int i , j , k , u ;
 for( i = 0 ; i < n ; i++ )
 {
  dist[ i ] = edge[ v0 ][ i ] ;
  if( i != v0 && dist[ i ] < INF )
   path[ i ] = v0 ;
  else
   path[ i ] = -1 ;
 }
 for( k = 2 ; k < n ; k++ )
 {
  for( u = 0 ; u < n ; u++ )
  {
   if( u != v0 )
   {
    for( j = 0 ;  j < n ; j++ )
    {
     if( edge[ j ][ u ] < INF && dist[ j ] + edge[ j ][ u ] < dist[ u ] )
     {
      dist[ u ] = dist[ j ] + edge[ j ][ u ] ;
      path[ u ] = j ;
     }
    }
   }
  }
 }
}

int main()
{
 int i , j ;
 int u , v , w ;
 scanf( "%d" , &n ) ;
 while( 1 )
 {
  scanf( "%d%d%d" , &u , &v , &w ) ;
  if( u == -1 && v == -1 && w == -1 )
   break ;
  edge[ u ][ v ] = w ;
 }
 for( i = 0 ; i < n ; i++ )
 {
  for( j = 0 ; j < n ; j++ )
  {
   if( i == j )
    edge[ i ][ j ] = 0 ;
   else
    if( edge[ i ][ j ] == 0 )
     edge[ i ][ j ] = INF ;
  }
 }
 bellman( 0 ) ;
 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 ] ) ;
 } 
 return 0 ;
}

7[html] 
<SPAN style="FONT-FAMILY: Arial, Helvetica, sans-serif">0 1 6</SPAN> 

0 1 6[html] 
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 

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