Jednoduchý kompletný ovahovaný graf je zadaný maticou susednosti, kde jednotlivé poličká udávajú cenu prechodu po hrane. Pre každú dvojiciu vrcholov zistite dĺžku najkratsej cesty.
Prvý riadok obsahuje prirodzené číslo $n$ ($1 \leq n \leq 1000$), udávajúce počet vrcholov grafu.
Nasledujúce $n$ riadkov obsahujú $n$ čísel, kde číslo v $i$-tom riadku a $j$-tom stlpci udáva cenu hrany medzi vrcholmi $i$ a $j$. Graf je jednoduchý, a preto poličká $(i, j)$ a $(j, i)$ sú zhodné. Všetky čísla sú nezáporné.
Výstup má obsahovať $n$ riadkov, na každom $n$ čísel, kde číslo v $i$-tom riadku a $j$-tom stlpci udáva dĺžku najkratšej cesty z vrcholu $i$ do vrcholu $j$.
5
0 1 1 100 1
1 0 1 1 1
1 1 0 1 1
100 1 1 0 1
1 1 1 1 0
0 1 1 2 1
1 0 1 1 1
1 1 0 1 1
2 1 1 0 1
1 1 1 1 0