11.3.1

import java.util.Scanner;
import java.io.PrintWriter;

import static javafx.scene.input.KeyCode.V;

/**
 * Created by Сергей on 27.05.2016.
 */
public class Solution321 {
    public static void main(String Args[]){
        Scanner sc=new Scanner(System.in);
        PrintWriter printWriter = new PrintWriter(System.out);
        int vCount=sc.nextInt();
        // Граф будем хранить в матрице смежности
        int[][] D = new int[vCount][vCount];
        for (int i = 0; i < vCount; i++) {
            for (int j = 0; j < vCount; j++) {
                // Считываем вес ребра между ве
                // ршинами
                // i и j соответственно
                D[i][j] = sc.nextInt();
                if (D[i][j]==-1) D[i][j]=9999999;
            }
        }

        for (int i=0; i<vCount; i++) D[i][i]=0;

        // Согласно алгоритму будем обновлять
        // ответ для каждой пары вершин i и j,
        // перебирая промежуточную вершину k
        for (int k=0; k<vCount; k++)
            for (int i=0; i<vCount; i++)
                for (int j=0; j<vCount; j++)
                    if (D[i][k]>0 && D[k][j]>0 && i!=j)
                        if (D[i][k]+D[k][j]<D[i][j] || D[i][j]==0)
                            D[i][j]=D[i][k]+D[k][j];

        for (int i = 0; i < vCount; i++) {
            for (int j = 0; j < vCount; j++){
                if (D[i][j]==9999999) D[i][j]=0;
            }
        }
        for (int i = 0; i < vCount; i++) {
            for (int j = 0; j < vCount; j++) {
                    printWriter.print(D[i][j] + " ");
            }
            printWriter.println();
        }
         int max=0;
        for (int i = 0; i < vCount; i++) {
            for (int j = 0; j < vCount; j++) {
                if (max < D[i][j]) max = D[i][j];
            }
        }
        printWriter.println(max);

        // После выполнения программы необходимо закрыть
        // потоки ввода и вывода
        sc.close();
        printWriter.close();
    }
}