Задача №112650. Электрификация

В Простоквашино решили провести электрификацию: подвести электричество ко всем домам. При этом точки стыковки линий электропередач могут находиться только около домов (линии не могут пересекаться и разветвляться в поле). Электростанция тоже находится около одного из домов. Напишите программу, которая строит сеть линий электропередач минимальной общей длины в Простоквашино.

Входные данные

В первой строке вводится количество домов N ( 1 ≤ N ≤ 1000 ). В следующих N строках записано по N чисел, разделённых пробелами – элементы весовой матрицы графа, который описывает схему возможных соединений домов. Число в матрице обозначает расстояние между домами, ноль – линию провести невозможно.

Выходные данные

Программа должны вывести все пары номеров домов, между которыми нужно построить линии электропередач. Они должны быть отсортированы следующим образом. В каждой паре сначала записывается меньший номер дома, потом – больший. Среди пар сначала идут пары с меньшим первым номером, среди них – сначала пары с меньшими вторыми номерами домов. Нумерация домов начинается с единицы.

Примеры
Входные данные
6
0 2 4 0 0 0
2 0 1 0 0 0
4 1 0 5 6 0
0 0 5 0 2 1
0 0 6 2 0 3
0 0 0 1 3 0
Выходные данные
1 2
2 3
3 4
4 5
4 6
Сдать: для сдачи задач необходимо войти в систему