Neighbouring Towns

A road map comes with a table that gives, for every pair of towns, the length of the shortest route between them. All roads are two-way, so the table is symmetric, and the distance from a town to itself is $0$.

The towns have a special property: whenever the shortest distance from town $A$ to town $B$ equals the shortest distance from $A$ to $C$ plus the shortest distance from $C$ to $B$, some shortest route from $A$ to $B$ passes through town $C$.

Two towns $A$ and $B$ are called neighbouring towns when no other town lies between them on a shortest route, that is, when there is no town $C$ (different from $A$ and $B$) for which

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

Given the distance table, find every pair of neighbouring towns.

Your program reads the table of distances from standard input, finds all pairs of neighbouring towns, and writes them to standard output.

The first line contains an integer $n$ ($1 \le n \le 200$), the number of towns; the towns are numbered from $1$ to $n$.

Each of the next $n$ lines contains $n$ non-negative integers no greater than $200$, separated by single spaces. The $j$-th integer on the $i$-th of these lines is the shortest distance between town $i$ and town $j$. The diagonal entries are $0$ and the table is symmetric.

Print every pair of neighbouring towns, one pair per line. Within a pair, print the two town numbers in increasing order, separated by a single space. List each pair only once.

Order the lines so that a pair $(a, b)$ comes before a pair $(c, d)$ when $a < c$, or when $a = c$ and $b < d$.

If there are no neighbouring pairs, print nothing.