Floyd - 1

Input

La prima riga contiene il numero di vertici n~(1 \le n \le 100) nel grafo. Ciascuna delle successive $n$ righe contiene $n$ numeri interi che descrivono la matrice di adiacenza del grafo: il $j$-esimo numero nella $i$-esima riga è il peso dell'arco dal vertice $i$ al vertice $j$. Il valore assoluto di ciascun numero non supera $100$. Gli elementi diagonali della matrice sono sempre uguali a zero.

Output

Stampare $n$ righe con $n$ numeri interi ciascuna — la matrice delle distanze minime tra tutte le coppie di vertici. Il $j$-esimo numero nella $i$-esima riga deve essere uguale alla lunghezza del cammino minimo dal vertice $i$ al vertice $j$.

Esempi