// Corrige aimablement redige par Louis Granboulan

import java.io.*;

class Graphe {
    int nb_som;
    int mat[][];

    Graphe (int n){
        nb_som = n;
        mat = new int[n][n];
    }
}

public class Corrige9 {

    public static String Lire () {
        BufferedReader in = 
            new BufferedReader(new InputStreamReader(System.in));
        String s;
        try { s = in.readLine(); }
        catch (IOException e) { s = "echec"; }
        return(s);
    }

    public static Graphe saisit () {
        Graphe a = new Graphe(Integer.parseInt(Lire()));
        for (int i=0; i<a.nb_som; i++)
            for (int j=0; j<a.nb_som; j++)
                a.mat[i][j] = Integer.parseInt(Lire()); 
        return(a);
    }

    public static void affiche (Graphe a) {
        for (int i=0; i<a.nb_som; i++) {
            for (int j=0; j<a.nb_som; j++)
                System.out.print(a.mat[i][j] + " "); 
            System.out.println(); 
        }
    }

    public static void f (Graphe a) {
        for (int i=a.nb_som-1; i>0; i=i-1) {
            int j = 0;
            while (j<a.nb_som && a.mat[i][j]==0)
                j = j + 1;
            if (j==a.nb_som)
                System.out.println(-1); 
            else
                System.out.println(j); 
        }
    }

    // La matrice de sortie contient
    //  - un 0 s'il n'existe pas de chemin
    //  - un entier positif qui est la longueur du chemin le plus court,
    //    en nombre d'arêtes parcourues
    // NB: on ne considère pas les chemins de longueur 0, ceux qui ne
    // passent par aucune arête et restent sur le sommet de départ !
    public static Graphe pluscourts (Graphe a) {
        Graphe res = new Graphe(a.nb_som); // résultat
        int i, j, k; // Compteurs
        for (i=0; i<a.nb_som; i++) 
            for (j=0; j<a.nb_som; j++)
                res.mat[i][j] = a.mat[i][j];
        for (k=0; k<a.nb_som; k++) 
            for (i=0; i<a.nb_som; i++) 
                for (j=0; j<a.nb_som; j++)
                    res.mat[i][j] =
                        specmin(res.mat[i][j],res.mat[i][k],res.mat[k][j]);
        return(res);
    }

    // Calcule le min de a et b+c, sachant que 0 représente l'infini
    public static int specmin (int a, int b, int c) {
      if (b==0) return a;
      if (c==0) return a;
      if (a==0) return b+c;
      if (a<b+c) return a; else return b+c;
    }

    // Autre façon de faire le calcul : on sait que les plus courts
    // chemins sont de longueur inférieure à a.nb_som
    public static Graphe pluscourts2 (Graphe a) {
        Graphe res = new Graphe(a.nb_som); // résultat
        int i, j, k; // Compteurs
        for (i=0; i<a.nb_som; i++) 
            for (j=0; j<a.nb_som; j++)
                if (a.mat[i][j] == 0)
                    res.mat[i][j] = a.nb_som;
                else
                    res.mat[i][j] = a.mat[i][j];
        for (k=0; k<a.nb_som; k++) 
            for (i=0; i<a.nb_som; i++) 
                for (j=0; j<a.nb_som; j++)
                    res.mat[i][j] =
                        min(res.mat[i][j],res.mat[i][k]+res.mat[k][j]);
        for (i=0; i<a.nb_som; i++) 
            for (j=0; j<a.nb_som; j++)
                if (res.mat[i][j] == a.nb_som)
                    res.mat[i][j] = 0;
        return(res);
    }

    // Calcule le min de a et b
    public static int min (int a, int b) {
      if (a<b) return a; else return b;
    }

    public static void main (String[] args) {
        Graphe g = saisit();
        affiche(g); 
        f(g);
        System.out.println("Première fonction");
        affiche(pluscourts(g)); 
        System.out.println("Seconde fonction");
        affiche(pluscourts2(g)); 
    }
}