Minimum weight spread for strong connectivity

There is a directed weighted graph with $N$ vertices numbered 0 to $N-1$. For every ordered pair of distinct vertices $x$ and $y$ there is one edge from $x$ to $y$, so the graph has $N \times (N-1)$ edges in total.

Choose some of these edges to build a new graph. Using only the chosen edges, a path from any vertex $u$ to any vertex $v$ must always exist. For example, when $N=3$ you may choose $0 \Rightarrow 1$, $1 \Rightarrow 0$, $0 \Rightarrow 2$, $2 \Rightarrow 0$, and you may also choose $0 \Rightarrow 1$, $1 \Rightarrow 2$, $2 \Rightarrow 0$.

Among the chosen edges, make the difference between the largest weight and the smallest weight as small as possible. Find the minimum of that difference over all valid choices. When $N=1$ there is no edge to choose, so the answer is 0.

The first line contains $N$, a natural number at most 50.

Each of the next $N$ lines holds one row of the weight matrix. The $y+1$-th value from the left on the $x+1$-th of these lines is the weight of the edge from vertex $x$ to vertex $y$. Every weight is an integer between 0 and 150,000. The self loop from vertex $x$ to vertex $x$ is always given as 0, and self loops cannot be chosen.

Print one integer, the minimum possible difference between the largest and the smallest chosen weight.