import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.*;
class Pair{
    int a;
    int b;
    int w;
    Pair(int a,  int b, int w){
        this.a = a;
        this.b = b;
        this.w = w;
    }
    public String toString(){
        return ("Weight" + w);
    }
}

public class Main {

	static List<Pair>  list;
    static int[] dist;
    static int[][] d;
    static int nrn, nrm;
    static void readFromFile() throws IOException{
		FileReader file = new FileReader("bellmanford.in");
	    BufferedReader buff = new BufferedReader(file);
		int i, a, b, c;
		
	    String[] line;
	    line = buff.readLine().split(" ");
	    nrn = Integer.parseInt(line[0]);
	    nrm = Integer.parseInt(line[1]);
	    list = new ArrayList<Pair>(nrm);
	    dist = new int[nrn];
	    for(i =0; i< nrm ; i++){
	    	line = buff.readLine().split(" ");
	    	a = Integer.parseInt(line[0]);
	    	b = Integer.parseInt(line[1]);
	    	c = Integer.parseInt(line[2]);
	    	list.add(new Pair(a, b,c));
	    }
	    buff.close();
	    
	    
    }
    static void readFromFile1() throws IOException{
		FileReader file = new FileReader("royfloyd.in");
	    BufferedReader buff = new BufferedReader(file);
		
	    String[] line;
	    line = buff.readLine().split(" ");
	    nrn = Integer.parseInt(line[0]);
	    d = new int[nrn][nrn];
	    for (int k = 0; k < nrn; k++){
	    	line = buff.readLine().split(" ");
	    	for (int i = 0; i < nrn; i++){
	    		d[k][i] = Integer.parseInt(line[i]);
	    	}
	    }
	    buff.close();
	    
    }
    static void doford() throws IOException{
    	int i, j;
    	FileWriter fw = new FileWriter("bellmanford.out");
		BufferedWriter bw = new BufferedWriter(fw);
		dist[0] = 0;
    	for( i=1; i< nrn; i++)
            dist[i] = Integer.MAX_VALUE;
        for(j = 0; j< nrm; j++){
        	if(list.get(j).a == 1)
        		dist[list.get(j).b-1] = list.get(j).w;
        }
        
        for(i =0; i < nrn -1; i++){
        	for(j =0; j< nrm ; j++){
        		if(dist[list.get(j).b-1] > dist[list.get(j).a-1] + list.get(j).w ){
        			dist[list.get(j).b-1]  = dist[list.get(j).a-1] + list.get(j).w;
        		}
        	}	
        }
        for(i =0; i< nrm; i++){
        	if(dist[list.get(i).b-1] > dist[list.get(i).a-1] + list.get(i).w ){
        		bw.write("Ciclu negativ!");
        		bw.close();
        		return;
        	}
        }
        for(i =1; i< nrn; i++){
        	bw.write(String.valueOf(dist[i]) + " ");
        }
        bw.close();
    }
    
    static void floyd() throws IOException{
    	

		for (int k = 0; k < nrn; k++)
			for (int i = 0; i < nrn; i++)
				for (int j = 0; j < nrn; j++)
					if (d[i][k] != 0 && d[k][j]!= 0 && (d[i][j] > d[i][k] + d[k][j] || d[i][j] == 0) && i != j)
						d[i][j] = d[i][k] + d[k][j];
		FileWriter fw = new FileWriter("royfloyd.out");
		BufferedWriter bw = new BufferedWriter(fw);
		for (int k = 0; k < nrn; k++){
			for (int i = 0; i < nrn; i++)
				bw.write(String.valueOf(d[k][i]) + " ");
			bw.newLine();
		}
		bw.close();
    }
    
    public static void main(String[] args) throws IOException {
		readFromFile1();
		floyd();
	}
}