# Floyd - Warshall + Transitive closure

# Floyd - 1

The complete directed weighted graph is given with the adjacency matrix. Construct a matrix of shortest paths between its vertices. It is guaranteed that the graph does not contain cycles of negative weight.

#### Input

The first line contains the number of vertices **n** (**1** ≤ **n** ≤ **100**) in a graph. Each of the next **n** lines contains **n** numbers and describes the adjacency matrix (the **j**-th number in the **i**-th row gives the weight of the edge from vertex **i** to vertex **j**). All the numbers by the absolute value does not exceed **100**. The numbers on the main diagonal are always zero.

#### Output

Print **n** rows with **n** numbers - the matrix of shortest distances between pairs of vertices. The **j**-th number of the **i**-th row must be equal to the weight of the shortest path from vertex **i** to vertex **j**.

4 0 5 9 100 100 0 2 8 100 100 0 7 4 100 100 0

0 5 7 13 12 0 2 8 11 16 0 7 4 9 11 0