Perishable Roads

Never라는 나라에는 n개의 도시와 잘 발달된 도로 체계가 있다. 모든 도시 쌍 사이에는 정확히 하나의 양방향 도로가 있으므로, 도로가 무려 개나 있다! 어떤 두 도로도 교차하지 않으며, 어떤 도로도 중간에 다른 도시를 지나지 않는다. Never인들은 터널과 다리를 건설하는 기술을 완전히 익혔다.

독립 위원회는 Never의 각 도로를 도로의 소멸성이라고 부르는 양의 정수로 평가했다. 도로의 소멸성이 낮을수록 그 도로를 따라 운전하는 것이 더 쾌적하다.

지금 Never는 교통의 해를 맞았다. 도시 중 하나에 교통 박물관을 세우고, 나머지 각 도시에 어떤 도시를 가리키는 표지판을 하나씩 설치하기로 했다. 표지판이 가리키는 도시는 반드시 박물관이 있는 도시일 필요는 없다. 표지판은 다음의 중요한 조건을 만족해야 한다. 박물관이 없는 도시에 사는 임의의 Never인이 그 도시에서 출발해 표지판의 방향을 따라 이동하면, 이 사람은 결국 박물관이 있는 도시에 도착해야 한다.

Never인들은 놀라울 정도로 긍정적으로 생각한다. Never인이 여러 도로로 이루어진 경로를 따라 이동한다면, 그 경로의 소멸성은 경로에 포함된 모든 도로의 소멸성 중 최솟값과 같다고 생각한다.

Never 정부는 아직 박물관을 어디에 지을지 결정하지 않았으므로, 가능한 n가지 선택지를 모두 고려한다. 여행자들이 표지판의 방향을 엄격히 따를 때, Never의 나머지 모든 도시에서 박물관이 있는 도시까지 가는 경로들의 소멸성 합이 가장 중요하다. Never 정부는 시민들을 소중히 여기므로, 이 합이 최소가 되도록 표지판을 설치하려 한다. 박물관을 지을 수 있는 도시에 대한 가능한 n가지 선택지 모두에 대해 가능한 합의 최솟값을 구하도록 도와주자.

첫 번째 줄에는 Never의 도시 수를 나타내는 하나의 정수 n (2 ≤ n ≤ 2000)가 주어진다.

이어지는 n - 1개의 줄에는 도로망에 대한 설명이 주어진다. 이 줄들 중 i-th에는 n - i개의 정수가 주어진다. i-th번째 줄의 j-th번째 정수는 도시 i와 i + j 사이 도로의 소멸성을 나타낸다.

모든 도로의 소멸성은 1 이상 109 이하이다.

1부터 n까지 각 도시에 대해 순서대로, 이 합이 최소가 되도록 표지판을 설치했을 때 Never의 나머지 모든 도시에서 해당 도시까지 가는 경로들의 소멸성 합으로 가능한 최솟값을 출력한다.

첫 번째 예제는 아래 그림으로 설명된다. 왼쪽부터 차례대로 초기 도로망과 박물관을 각각 도시 1, 2, 3에 지었을 때 표지판의 최적 방향이 나타나 있다. 박물관이 있는 도시는 파란색 원으로, 표지판의 방향은 초록색 화살표로 표시된다.

예를 들어 박물관을 도시 3에 지으면 도시 1의 표지판은 도시 3을 가리켜야 하고, 도시 2의 표지판은 도시 1을 가리켜야 한다. 그러면 도시 1에서 도시 3까지의 경로의 소멸성은 2이고, 도시 2에서 도시 3까지의 경로의 소멸성은 1이다. 이 경로들의 소멸성 합은 3이다.