코드의 오류

한 초보 프로그래머가 C++로 프로그램을 작성했다.

• 먼저 프로그램은 $N$개 노드로 이루어진 무방향 그래프의 인접 행렬을 읽어 32비트 정수 배열 $g$에 저장한다. 값을 읽고 나면 $g[u][v]$는 노드 $u$와 $v$ 사이에 간선이 있으면 1, 없으면 9999이다 ($1 \leq u \neq v \leq N$). 행렬의 주대각선은 0으로 이루어져 있다.
• 그래프를 읽은 뒤 프로그램에서 다음 코드가 실행된다.

  for (int w = 1; w < N; w = w + 1) {
      for (int u = 1; u < N; u = u + 1) {
          for (int v = 1; v < N; v = v + 1) {
              g[u][v] = min(g[u][v], g[u][w] + g[w][v]);
          }
      }
  }
  

• 그런 다음 결과 행렬을 파일에 쓴다.

프로그래머는 여러 그래프에 대해 프로그램을 실행했고, 지루한 기다림 끝에 결과를 확인했다. 물론 실망스러운 결과였다. 짐작했겠지만 프로그래머가 원한 것은 그래프의 모든 노드 사이 최단 거리 행렬이었다. 그러나 프로그램에는 결함이 있었다. 프로그래머가 직접 고칠 수도 있지만, 프로그램이 결과를 다시 계산하기를 기다리는 데는 너무 많은 시간이 든다. 여러분은 불운한 프로그래머의 코드가 낸 결과를 받아 최단 거리 행렬을 출력하는 프로그램을 작성해야 한다.

입력 파일의 첫 줄에는 정수 $N$이 하나 주어진다 ($1 \leq N \leq 2\,000$). 다음 $N$개 줄의 $i$번째 줄에는 $N$개의 수가 주어지며, $j$번째 수는 위 알고리즘을 실행한 뒤의 $g[i][j]$이다 ($0 \le g[i][j] \le 9999$).

$N$개 줄을 출력한다. $i$번째 줄에는 공백으로 구분된 수 $N$개를 출력하며, $j$번째 수는 그래프에서 노드 $i$와 $j$ 사이 최단 경로의 길이이고, 두 노드 사이에 경로가 없으면 9999이다.