Зруйнування доріг#1617
У країні між кожною парою міст існує пряма двостороння дорога. Петро хоче підірвати набір доріг так, щоб існувало принаймні два міста, між якими неможливо дістатися.
Вам задано вартість підриву кожної дороги. Знайдіть мінімальну загальну вартість, щоб Петро досягнув своєї мети.
Вхід складається з кількох тестових випадків. Перший рядок кожного тесту містить число (n \leq 50) — кількість міст у країні. Далі йдуть рядків, що описують дороги: -ий символ -го рядка — це цифра, що означає вартість підриву дороги між містами та .
Для кожного тестового випадку виведіть в окремому рядку мінімальну загальну вартість для Петра, щоб досягти своєї мети.
Приклад 1