뒤섞인 여정

몇몇 친구와 함께 Beautiful Authentic Parks Centre로 휴가를 떠날 계획이다. 거기 있는 동안 최대한 많은 공원을 둘러보고 싶다. 준비의 일환으로 당신과 가장 친한 친구는 공원들, 공원 사이의 도로, 그리고 도로의 길이를 담은 자세한 지도를 만들기로 했다. Parks Centre 방문객이 공원 사이를 끝없이 돌지 않도록, 공원 사이의 경로는 일방통행이며 같은 공원을 두 번 방문할 수 없게 만들어져 있다(즉, 대응하는 그래프는 비순환 그래프이다). 둘은 하루 종일 매우 상세하고 솔직히 꽤 큰 Parks Centre 지도를 만들었다.

그림 J.1: 샘플 입력 1에 대응하는 공원 지도.

다음 날 재앙이 닥친다. 친구가 그 번거로운 지도를 없앴다고 기쁘게 알린다! 대신 공원 사이의 평균 거리만 담은 단순한 표를 만들었는데, 각 도로에 같은 가중치를 준 값이다. 그래서 그림 J.1에서 공원 1과 4 사이의 평균 거리가 8이라고 한다. 경로가 3개이고 평균 길이가 (6 + 8 + 10)/3 = 8이기 때문이다. 기운이 빠지고 지도를 처음부터 다시 만들어야 한다는 생각에 질린다. 친구가 만든 평균 거리 표를 이용해 원래 지도를 복원해 보는 편이 쉬울지도 모른다. 기억나는 점은 하나다. 지도의 도로는 한 번도 비효율적이지 않았다. 두 공원 사이에 직접 도로가 있다면, 다른 공원을 하나 이상 거치는 모든 경로는 엄격하게 더 길었다. 이 조건은 첫 번째 샘플 입력에서 성립한다. 예를 들어 1에서 4로 가는 도로의 길이는 6이고, 1에서 4로 가는 다른 어떤 경로도 그보다 길다.

공원 사이의 평균 거리가 주어졌을 때, 이 평균 거리가 성립하는 원래 지도, 즉 가중치가 있는 유향 비순환 그래프를 출력하라.

원래 지도(원래 그래프)에 대해 다음 사실을 알고 있다.

• 도로를 따라가다가 한 번 떠난 공원으로 돌아올 방법은 없다. 즉 그래프는 비순환이다.
• 원래 그래프의 도로 길이는 모두 정수이다.
• 두 공원 사이에 서로 다른 경로는 최대 1000개이다.
• 직접 도로는 항상 효율적이다. 공원 i에서 공원 j로 가는 직접 도로가 있다면, i에서 j로 가는 다른 모든 경로는 그 직접 도로보다 엄격하게 길다.

첫 줄에 정수 $1 \le n \le 100$이 주어진다. 공원(정점)의 개수이다. 다음 $n$개 줄의 $i$번째 줄에는 정점 $i$에서 정점 $j$까지의 평균 거리가 $j$번째 수로 주어진다. 정점 $i$에서 $j$로 가는 경로가 없으면 -1이다. 모든 거리는 -1이거나 $10^{15}$ 이하의 음이 아닌 정수이다.

$n$줄을 출력한다. 각 줄에는 $n$개의 정수가 있다. $i$번째 줄의 $j$번째 수는 정점 $i$에서 정점 $j$로 가는 간선의 양의 길이이고, 그런 간선이 없으면 -1이다. 해가 존재함이 보장된다.