Задачи
Разрушение дорог
Разрушение дорог
Между каждой парой городов страны имеется прямая двусторонняя дорога. Петр хочет взорвать такое количество дорог, чтобы образовалось хотя бы два города, проезд между которыми был невозможен.
Вам известна стоимость подрыва каждой дороги. Найти наименьшую стоимость, за которую Петру удастся совершить задуманное.
Входные данные
Состоит из нескольких тестов. Первая строка каждого теста содержит количество n (n ≤ 50) городов в стране. Следующие n строк описывают дороги: j-ый символ i-ой строки является цифрой, задающей стоимость уничтожения дороги, ведущей из i-го города в j-ый.
Выходные данные
Для каждого теста вывести в отдельной строке наименьшую стоимость, за которую Петру удастся совершить задуманное.
Пример
Входные данные #1
4 0911 9011 1109 1190 6 030900 304120 040174 911021 027207 004170 4 0399 3033 9309 9390
Выходные данные #1
4 8 9