# Floyd - 1

A complete directed weighted graph is given by its adjacency matrix. Construct a matrix of the shortest paths between all pairs of its vertices. It is guaranteed that the graph has no cycles of negative weight.

## Input

The first line contains the number of vertices $n(1≤n≤100)$ in the graph. Each of the next $n$ lines contains $n$ integers and describes the adjacency matrix of the graph (the $j$-th number in the $i$-th row corresponds to the weight of the edge from vertex $i$ to vertex $j$). All numbers by the absolute value do not exceed $100$. The diagonal elements of the matrix are always zeros.

## Output

Print $n$ lines with $n$ integers — the matrix of the shortest distances between all pairs of vertices. The $j$-th number in the $i$-th row should equal the weight of the shortest path from vertex $i$ to vertex $j$.