Между каждой парой городов страны имеется прямая двусторонняя дорога. Петр хочет взорвать такое количество дорог, чтобы образовалось хотя бы два города, проезд между которыми был невозможен.
Вам известна стоимость подрыва каждой дороги. Найти наименьшую стоимость, за которую Петру удастся совершить задуманное.
Состоит из нескольких тестов. Первая строка каждого теста содержит количество n (n ≤ 50) городов в стране. Следующие n строк описывают дороги: j-ый символ i-ой строки является цифрой, задающей стоимость уничтожения дороги, ведущей из i-го города в j-ый.
Для каждого теста вывести в отдельной строке наименьшую стоимость, за которую Петру удастся совершить задуманное.