Сви најкраћи путеви у густом графу

На једној територији између свака два града постоји директан пут. Неки путеви су лошег квалитета, па је некад брже стићи од града до града ако се иде неким од околних путева. Ако је познато време да се пређе сваки од директних путева (оно може зависити и од смера у којем се пут прелази), напиши програм који за сваки пар градова одређује колико се времена може уштедети ако се не иде директним путем.

Улаз

Са стандардног улаза се учитава број градова \(n\) (\(3 \leq n \leq 400\)), а након тога квадратна матрица димензије \(n \times n\) која садржи времена у секундама потребна да се директним путем стигне од града до града (на дијагонали се налазе нуле, а остала времена су цели бројеви између \(60\) и \(3600\)).

Излаз

На стандардни излаз исписати квадратну матрицу која садржи уштеде за сваки пар градова.

Пример

Улаз

4
0 190 300 120
180 0 240 350
290 430 0 80
120 170 90 0

Излаз

0 0 90 0 
0 0 0 50 
90 180 0 0 
0 0 0 0

Објашњење

Од града 1 до града 3 боље је ићи преко града 4 (уместо 300 секунди путује се 120 + 90 = 210 секунди). И од града 3 до града 1 боље је ићи преко града 4 (уместо 290 секунди путује се 80 + 120 = 200 секунди). Од града 2 до града 4 најбоље је ићи преко града 1 (уместо 350 секунди путује се 120 + 180 = 300 секунди). Од града 3 до града 2 најбоље је ићи преко града 4 (уместо 430 секунди путује се 80 + 170 = 250 секунди).