public class FloydWarshallTest {
    static final int INF = 99999;      // 도달할 수 없는 경로의 가중치(오버플로우가 발생하지 않도록 Integer.MAX_VALUE 설정하지 않음)
    static int N;
    static int[][] dp;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        dp = new int[N][N];

        // 경로 비용 초기화
        for (int i=0; i<N; i++) {
            for (int j=0; j<N; j++) {
                dp[i][j] = sc.nextInt();
                if (i != j && dp[i][j] == 0) dp[i][j] = INF;    // 도달할 수 없는 경로는 비용을 최대로 초기화
            }
        }

        positiveFloydWarshall();        // 양의 가중치 최단 경로
        negativeFloydWarshall();        // 음의 가중치 최단 경로

    }

    // 양의 가중치 최단 경로
    public static void positiveFloydWarshall() {
        for (int k=0; k<N; k++) {
            for (int i=0; i<N; i++) {
                if (i == k) continue;                    // 경유지 = 출발지인 경우 pass
                for (int j=0; j<N; j++) {
                    // if (i == j || i == j) continue;   // 경유지 = 도착지인 경우, 출발지 = 도착지인 경우 pass. 하지만 어차피 자기자신으로의 이동은 비용이 0이므로 생략 가능
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }   
    }

    // 음의 가중치 최단 경로
    public static void negativeFloydWarshall() {
        for (int k=0; k<N; k++) {
            for (int i=0; i<N; i++) {
                if (i == k) continue;                          // 경유지 = 출발지인 경우 pass
                for (int j=0; j<N; j++) {
                    if (i == j) continue;                      // 출발지 = 도착지인 경우
                    if (dp[i][k] != INF && dp[k][j] != INF)    // 음의 가중치는 도달할 수 없는 경로의 비용도 감소시켜 도달할 수 있는 것처럼 만들 수 있으므로 애초에 도달할 수 없는 곳은 pass
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }
    }
}