12880번 - 그래프 차이 최소

0번부터 N-1번까지 번호가 있는 정점들로 구성된 방향성 가중치 그래프가 있다. 서로 다른 모든 정점 사이에 방향성 가중치 간선이 있다. 따라서 간선은 총 N*(N-1)개가 존재한다. 이 중 몇 개의 간선을 선택하여, 임의의 두 정점을 선택하였을 때에 항상 경로가 있도록 선택해야 한다. 예를 들어 N=3일 때에 가능한 간선 선택으로, 0 ⇒ 1, 1 ⇒ 0, 0 ⇒ 2, 2 ⇒ 0이 있고, 또는 0 ⇒ 1, 1 ⇒ 2, 2 ⇒ 0도 가능하다. 선분 선택을 마치고 새로이 생성되는 그래프의 가장 큰 가중치 값과 가장 작은 가중치 값 차이를 최소화하고 싶다. 가능한 선택에서의 가중치 최대 최소 차이의 최솟값을 구하시오.

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

둘째 줄부터 N개의 줄에 걸쳐 각 간선의 가중치가 주어진다. x+1번째 행의 y번째 값은 정점 x에서 정점 y로 향하는 간선의 가중치이다. 각 간선의 가중치 값은 0 이상 150,000 이하이며, 정점 x에서 정점 x에 이르는 간선(self loop)은 가중치가 항상 0으로 주어진다.

문제의 정답이 되는 하나의 정수를 출력한다.