Ölkənin hər bir şəhərlər cütlüyü arasında düz iki istiqamətli yol var. Petr müəyyən sayda yolları elə partlatmaq istəyir ki, heç olmazsa elə iki şəhər olsun ki, onlar arasında gediş olmasın.

Sizə hər bir partlayışın qiyməti məlumdur. Petrin düşündüyünü həyata keçirə bilməsi üçün minimal qiymət tapın.

Giriş verilənləri

Giriş verilənləri bir neçə test ehtiva edir. Hər bir testin ilk sətri ölkədəki şəhərlərin n (n ≤ 50) sayını ehtiva edir. Növbəti n sətir yolları əks etdirir: i sətrinin j-ci işarəsi i şəhərindən j şəhərinə aparan yolun dağıdılmasının qiymətini verən rəqəmdir.

Çıxış verilənləri

Hər bir test üçün ayrı sətirdə Petrin düşündüyünü həyata keçirməsi üçün minimal qiyməti verməli.