public class FloydWarshall {

	public static void floydWarshall(int[][] graph){
		int N = graph.length;
		int dist[][] = new int[N][N];
		for(int i=0;i<N;i++){
			for(int j=0;j<N;j++){
				dist[i][j] = graph[i][j];
			}
		}
			
		for(int k=0;k<N;k++){
			for(int i=0;i<N;i++){
				for(int j=0;j<N;j++){
					if(dist[i][j]!=-999)
					dist[i][j] = Math.max(dist[i][k]+dist[k][j],dist[i][j]);
				}
			}
		}
		
		for(int i=0;i<N;i++){
			System.out.println();
			for(int j=0;j<N;j++){
				System.out.print(" "+dist[i][j]+" ");;
			}
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		 int graph[][] = {{-999,-999,-999,-999},
		                 {3,4,5,-999},
		                 {40,8,9,10},
		                 {-999,1,2,3}
               };
		 floydWarshall(graph);
	}

}