Qədim Azərbaycan
Mənbəyi məlum olmayan məlumatlara görə, çox uzun illər əvvəl Azərbaycanda N şəhər yerləşib. Buşəhərlərin bəzilərinin arasında ikitərəfli yol var imiş. Arxeoloq Barışın tapdıqlarına görə, bu N şəhərin istənilən birindən digər bütün şəhərlərə səyahət etmək olurdu (səyahət birbaşa olmaya da bilər).
Təəssüf ki, aralarında birbaşa yol olan şəhərlər və bu yolların uzunluqları unudulub, amma Barış araşdırmalarını davam etdirərək istənilən iki şəhər arasındakı ən qısa məsafəni tapdı və N × N ölçülü A cədvəlini düzəltdi. Cədvəldə A[ij] ədədi i və j şəhərləri arasındakı ən qısa məsafəni göstərir.
Bu məlumatlara əsaslanaraq, Barışa belə N şəhərin mümkün olub olmadığını tapmaqda kömək edin. Əgərbelə şəhərlərin mövcudluğu mümkündürsə, oradakı bütün yolların uzunluqları cəminin ola biləcək ənkiçik qiymətini tapın.
Giriş verilənləri
İlk sətirdə bir tam ədəd N (1 ≤ N ≤ 200) – şəhərlərin sayı, növbəti N sətrin hər birində isə N sayda ədəd A[ij] (1 ≤ A[ij] ≤ 10^9 (i≠j), A[ii] = 0) – i və j şəhərləri arasındakı ən qısa məsafə verilir.
Çıxış verilənləri
Əgər belə N şəhərin mövcudluğu mümkün deyilsə, "-1", əks halda isə yolların uzunluqları cəminin ola biləcək ən kiçik qiymətini çap edin.