강한 연결을 만드는 가중치 차이 최소화

0번부터 $N-1$번까지 번호가 붙은 정점 $N$개로 이루어진 방향 가중치 그래프가 있다. 서로 다른 두 정점 $x$, $y$의 순서쌍마다 $x$에서 $y$로 가는 간선이 하나씩 있으므로 간선은 모두 $N \times (N-1)$개다.

이 간선 중 일부를 골라 새 그래프를 만든다. 고른 간선만 사용해서 임의의 정점 $u$에서 임의의 정점 $v$로 가는 경로가 항상 존재해야 한다. 예를 들어 $N=3$이면 $0 \Rightarrow 1$, $1 \Rightarrow 0$, $0 \Rightarrow 2$, $2 \Rightarrow 0$을 고를 수 있고, $0 \Rightarrow 1$, $1 \Rightarrow 2$, $2 \Rightarrow 0$을 고를 수도 있다.

고른 간선의 가중치 중 최댓값과 최솟값의 차이를 가장 작게 만들고 싶다. 가능한 모든 선택에서 그 차이의 최솟값을 구하시오. $N=1$이면 고를 간선이 없으므로 답은 0이다.

첫째 줄에 $N$이 주어진다. $N$은 50 이하의 자연수다.

둘째 줄부터 $N$개의 줄에 가중치 행렬이 주어진다. 위에서 $x+1$번째 줄의 왼쪽에서 $y+1$번째 값은 정점 $x$에서 정점 $y$로 가는 간선의 가중치다. 가중치는 0 이상 150,000 이하의 정수다. 정점 $x$에서 정점 $x$로 가는 자기 간선의 값은 항상 0으로 주어지며, 자기 간선은 고를 수 없다.

가중치 최댓값과 최솟값 차이의 최솟값을 정수 하나로 출력한다.