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 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ə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 (1 ≤ N ≤ 200) – şəhərlərin sayı, növbəti N sətrin hər birində isə N sayda ədəd Aij (1 ≤ Aij ≤ 109(i≠j), Aii = 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.