이웃한 도시

도로 지도에는 모든 도시 쌍 사이의 최단 경로 길이를 담은 표가 함께 주어진다. 모든 도로는 양방향이므로 이 표는 대칭이며, 어떤 도시에서 자기 자신까지의 거리는 $0$이다.

이 도시들에는 다음과 같은 특별한 성질이 있다. 도시 $A$에서 도시 $B$까지의 최단 거리가 $A$에서 $C$까지의 최단 거리와 $C$에서 $B$까지의 최단 거리를 더한 값과 같다면, $A$에서 $B$로 가는 어떤 최단 경로는 도시 $C$를 지난다.

두 도시 $A$와 $B$는, 최단 경로 위에서 둘 사이에 놓이는 다른 도시가 하나도 없을 때 서로 이웃한 도시라고 부른다. 즉 $A$, $B$와 다른 도시 $C$ 가운데

$\text{dist}(A, B) = \text{dist}(A, C) + \text{dist}(C, B)$

를 만족하는 $C$가 존재하지 않을 때이다.

거리 표가 주어질 때, 이웃한 도시 쌍을 모두 찾아라.

프로그램은 표준 입력에서 거리 표를 읽어 이웃한 도시 쌍을 모두 찾고, 그 결과를 표준 출력에 쓴다.

첫째 줄에 도시의 수 $n$ ($1 \le n \le 200$)이 주어진다. 도시는 $1$번부터 $n$번까지 번호가 매겨져 있다.

이어지는 $n$개의 줄에는 각각 $200$ 이하의 음이 아닌 정수 $n$개가 공백 하나로 구분되어 주어진다. 그중 $i$번째 줄의 $j$번째 정수는 도시 $i$와 도시 $j$ 사이의 최단 거리이다. 대각선 값은 $0$이고 표는 대칭이다.

이웃한 도시 쌍을 한 줄에 하나씩 모두 출력한다. 한 쌍에서 두 도시의 번호는 작은 수부터 오름차순으로, 공백 하나로 구분해 출력한다. 같은 쌍은 한 번만 출력한다.

출력하는 줄들은 쌍 $(a, b)$가 쌍 $(c, d)$보다 먼저 오도록 정렬한다. 여기서 먼저 온다는 것은 $a < c$이거나, $a = c$이면서 $b < d$인 경우를 뜻한다.

이웃한 도시 쌍이 하나도 없으면 아무것도 출력하지 않는다.