Aviabiletlər

Baş Mühəndis Peterə "Air Bubundiya" şirkəti üçün yeni bir təyyarə modeli hazırlamaq tapşırıldı. Məlum oldu ki, ən çətin hissə yanacaq çəninin optimal ölçüsünü seçməkdir.

"Air Bubundiya"nın Baş Kartoqrafı Con Bubundiyanın ətraflı xəritəsini hazırladı. Bu xəritədə o, istənilən iki şəhər arasında uçuş üçün tələb olunan yanacaq sərfiyyatını göstərdi.

Peter yanacaq çəninin ölçüsünü mümkün qədər kiçik etmək istəyir ki, təyyarə hər hansı şəhərdən digərinə (yolda şəhərlərdə yanacaq doldurmaq şərtilə) uça bilsin.

Giriş

Birinci sətirdə Bubundiyada şəhərlərin sayı $n$ (1 \leq n \leq 1000) verilir. Növbəti $n$ sətirin hər birində $n$ ədəd var. $i$-ci sətirdə $j$-ci ədəd $i$-ci şəhərdən $j$-ci şəhərə uçuş üçün tələb olunan yanacaq sərfiyyatını göstərir. Bütün ədədlər qeyri-mənfidir və 10^9-dan kiçikdir. Həmçinin, istənilən $i$ üçün $i$-ci sətirdə $i$-ci ədəd $0$-a bərabərdir.

Çıxış

Bir ədəd çap edin — yanacaq çəninin optimal ölçüsü.