import java.util.*;
import java.lang.*;
import java.io.*;
 
class Graph {
 
    public static void main(String[] args){
        Scanner input =  new Scanner(System.in);
 
        int n, max = 0;
        n = input.nextInt();
        int[][] matrix = new int[n][n];
 
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                matrix[i][j] = input.nextInt();
            }
        }
 
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                for(int k = 0; k < n; k++){
                    if(j != k && matrix[j][i] != -1 && matrix[i][k] != -1){
                        if(matrix[j][k] == -1)
                            matrix[j][k] = matrix[j][i] + matrix[i][k];
                        else
                            matrix[j][k] = Math.min(matrix[j][k], matrix[j][i] + matrix[i][k]);
                    }
                }
            }
        }
 
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] > max) max = matrix[i][j];
            }
        }
 
        System.out.println(max);
    }
}

aW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgpjbGFzcyBHcmFwaCB7CgogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncyl7CiAgICAgICAgU2Nhbm5lciBpbnB1dCA9ICBuZXcgU2Nhbm5lcihTeXN0ZW0uaW4pOwoKICAgICAgICBpbnQgbiwgbWF4ID0gMDsKICAgICAgICBuID0gaW5wdXQubmV4dEludCgpOwogICAgICAgIGludFtdW10gbWF0cml4ID0gbmV3IGludFtuXVtuXTsKCiAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKyl7CiAgICAgICAgICAgIGZvcihpbnQgaiA9IDA7IGogPCBuOyBqKyspewogICAgICAgICAgICAgICAgbWF0cml4W2ldW2pdID0gaW5wdXQubmV4dEludCgpOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgbjsgaSsrKXsKICAgICAgICAgICAgZm9yKGludCBqID0gMDsgaiA8IG47IGorKyl7CiAgICAgICAgICAgICAgICBmb3IoaW50IGsgPSAwOyBrIDwgbjsgaysrKXsKICAgICAgICAgICAgICAgICAgICBpZihqICE9IGsgJiYgbWF0cml4W2pdW2ldICE9IC0xICYmIG1hdHJpeFtpXVtrXSAhPSAtMSl7CiAgICAgICAgICAgICAgICAgICAgICAgIGlmKG1hdHJpeFtqXVtrXSA9PSAtMSkKICAgICAgICAgICAgICAgICAgICAgICAgICAgIG1hdHJpeFtqXVtrXSA9IG1hdHJpeFtqXVtpXSArIG1hdHJpeFtpXVtrXTsKICAgICAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgICAgICAgICAgbWF0cml4W2pdW2tdID0gTWF0aC5taW4obWF0cml4W2pdW2tdLCBtYXRyaXhbal1baV0gKyBtYXRyaXhbaV1ba10pOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgZm9yKGludCBpID0gMDsgaSA8IG47IGkrKyl7CiAgICAgICAgICAgIGZvcihpbnQgaiA9IDA7IGogPCBuOyBqKyspewogICAgICAgICAgICAgICAgaWYobWF0cml4W2ldW2pdID4gbWF4KSBtYXggPSBtYXRyaXhbaV1bal07CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbihtYXgpOwogICAgfQp9

MyAKMCAtMSAyCjIgMCAtMQo0IDEgMA==

3 
0 -1 2
2 0 -1
4 1 0