import java.io.RandomAccessFile;
import java.io.IOException;
import java.util.StringTokenizer;
import java.util.NoSuchElementException;

public class routing{
        public static void main( String args[] ){
                routing app = new routing( args[ 0 ] );
        }

        public routing( String inFile ){
                try{
                        RandomAccessFile file = new RandomAccessFile( inFile, "rw" );
                        String tmp = file.readLine(); int i = 0;
                        while( tmp != null ){ tmp = file.readLine(); i++; }

                        file.seek( 0 ); tmp = file.readLine();
                        int graph[][]; graph = new int[ i ][ i ]; i = 0;
                        while( tmp != null ){
                                StringTokenizer sT = new StringTokenizer( tmp, " " ); int j = 0;
                                while( sT.hasMoreTokens() ){ graph[ i ][ j++ ] = Integer.parseInt( sT.nextToken() ); }
                                i++; tmp = file.readLine();
                        }
                        file.close();

                        dijkstra( graph );
                }
                catch( IOException io ){ System.err.println( io.toString() ); System.exit( 1 ); }
                catch( RuntimeException re ){ System.err.println( re.toString() ); System.exit( 1 ); }
        }

        public void dijkstra( int graph[][] ){
                int d[] = new int[ graph.length ];
                int dC[] = new int[ graph.length ];
                int p[] = new int[ graph.length ];
                for( int i = 0; i < graph.length; i++ ){ d[ i ] = 100; dC[ i ] = 100; p[ i ] = -1; }
                d[ 0 ] = 0; dC[ 0 ] = 0;

                int i = 0, min = 200, pos = 0; //You can change the min to 1000 to make it the largest number
                while( i < graph.length ){
                        //extract minimum
                        for( int j = 0; j < dC.length; j++ ){
                                if( min > d[ j ] && dC[ j ] != -1 ){
                                        min = d[ j ]; pos = j;
                                }
                        }
                        dC[ pos ] = -1;

                        //relax
                        for( int j = 0; j < graph.length; j++ ){
                                if( d[ j ] > graph[ pos ][ j ] + d[ pos ] ){
                                        d[ j ] = graph[ pos ][ j ] + d[ pos ];
                                        p[ j ] = pos;
                                }
                        }
                        i++; min = 200;
                }



                for( int j = 0; j < p.length; j++ ){
                        System.out.print( p[ j ] + " " );
                }
                System.out.print( "\n" );
                for( int j = 0; j < d.length; j++ ){
                        System.out.print( d[ j ] + " " );
                }
                System.out.print( "\n" );
        }
}