Aviabiletlər
Baş konstruktor Petya "Air Bubundia" şirkəti üçün yeni bir təyyarə modeli hazırlamaq tapşırığını aldı. Məlum oldu ki, ən çətin məsələ yanacaq çəninin optimal ölçüsünü təyin etməkdir.
"Air Bubundia"nın baş kartoqrafı Vasya, Bubundiyanın ətraflı xəritəsini hazırladı. Bu xəritədə, hər bir şəhər cütü arasında uçuş üçün tələb olunan yanacaq miqdarını qeyd etdi.
Petya, təyyarənin istənilən şəhərdən digərinə (yolda yanacaq doldurmaq imkanı ilə) uça bilməsi üçün lazım olan minimum çən ölçüsünü müəyyənləşdirmək istəyir.
Giriş məlumatları
Birinci sətir Bubundiyada şəhərlərin sayını n (1 ≤ n ≤ 1000) göstərir. Sonrakı n sətir, hər birində n ədəd olmaqla gəlir. i-ci sətirdəki j-ci ədəd, i-ci şəhərdən j-ci şəhərə uçuş üçün tələb olunan yanacaq miqdarını göstərir. Bütün ədədlər sıfırdan böyükdür və 10^9-dan kiçikdir. Hər hansı bir i üçün i-ci sətirdə i-ci ədədin sıfıra bərabər olduğu təmin edilir.
Çıxış məlumatları
Bir ədəd - optimal çən ölçüsü.