e-olymp
Problems

Qədim Azərbaycan

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ə Aij ədədi ij şə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ər belə şəhərlərin mövcudluğu mümkündürsə, oradakı bütün yolların uzunluqları cəminin ola biləcək ən kiçik qiymətini tapın.

Giriş verilənləri

İlk sətirdə bir tam ədəd N (1N200) – şəhərlərin sayı, növbəti N sətrin hər birində isə N sayda ədəd Aij (1Aij109(i≠j), Aii = 0) – ij şə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.

Time limit 1 second
Memory limit 256 MiB
Input example #1
3
0 1 3
1 0 2
3 2 0
Output example #1
3

Input example #2
3
0 1 3
1 0 1
3 1 0
Output example #2
-1


Author Rafael Saddatimov
Source Azərbaycan Milli İnformatika Olimpiadası – Final Turu 5 May 2019