잃어버린 지도

세계의 어느 산악 지방에 n개의 마을이 있다. 이 마을들을 서로 잇는 도로가 여러 개 있으며, 각 도로는 항상 두 마을을 직접 연결하고 양방향으로 통행할 수 있다. 험준한 지형 때문에 도로를 놓는 데 드는 비용이 크므로, 모든 마을이 도로를 여러 번 거쳐 다른 모든 마을에 도달할 수 있도록 최소 개수의 도로만 건설되었다.

모든 마을이 같은 천연 자원을 공급받는 것은 아니므로 마을 간의 교역은 매우 중요하다. 그러나 같은 자원을 생산하는 마을이 많기 때문에, 마을들은 다른 마을까지의 상대적 거리를 알아 두면 전체 교역 비용을 줄일 수 있도록 교역 상대를 고를 수 있다. 두 마을 a와 b 사이의 거리는 a와 b를 잇는 최단 경로에 있는 각 도로 길이의 합이다.

모든 마을 쌍 사이의 거리를 계산하는 작업이 진행 중이었다. 이 정보는 마을의 배치와 마을 사이를 잇는 도로를 보여 주는 지도와 함께 표에 담겼다. 당신은 지역 경제를 개선하기 위해 이 표와 지도를 모든 마을에 배포하는 일을 맡았다.

그런데 이 일을 맡은 지 얼마 지나지 않아 돌풍이 불어 지도가 손에서 빠져나가 들판으로 날아가 버렸다. 아무리 찾아도 지도를 찾을 수 없었다. 모든 마을을 방문해 지도를 복원한 다음 지도와 표를 배포할 수도 있지만, 그러면 원래 작업보다 두 배의 시간이 걸리고 마을 사람들은 크게 불만을 품을 것이다. 표만으로 지도를 복원할 수 있지 않을까?

입력의 첫째 줄에는 이 지방의 마을 수를 나타내는 정수 n(2 ≤ n ≤ 2 500)이 주어진다. 다음 n개 줄에는 각각 n개의 정수가 주어진다. i번째 줄의 j번째 정수는 마을 i에서 마을 j까지의 거리이다. 모든 거리는 i = j인 경우를 제외하면 0보다 크고 107보다 작으며, 마을 i에서 마을 j까지의 거리는 마을 j에서 마을 i까지의 거리와 같다.

각 테스트 케이스마다 n − 1개 줄을 출력한다. 각 줄에는 두 정수 u와 v를 출력하는데, 이는 이 지방에서 마을 u와 마을 v를 잇는 도로가 있다는 뜻이다. 마을 번호는 1부터 n까지라고 가정한다. 원래 도로 집합을 출력하는 답이라면 무엇이든 정답으로 인정한다.