CF773D.Perishable Roads

In the country of Never, there are n cities and a well-developed road system. There is exactly one bidirectional road between every pair of cities, thus, there are as many as roads! No two roads intersect, and no road passes through intermediate cities. The art of building tunnels and bridges has been mastered by Neverians.

An independent committee has evaluated each road of Never with a positive integer called the perishability of the road. The lower the road's perishability is, the more pleasant it is to drive through this road.

It's the year of transport in Never. It has been decided to build a museum of transport in one of the cities, and to set a single signpost directing to some city (not necessarily the one with the museum) in each of the other cities. The signposts must satisfy the following important condition: if any Neverian living in a city without the museum starts travelling from that city following the directions of the signposts, then this person will eventually arrive in the city with the museum.

Neverians are incredibly positive-minded. If a Neverian travels by a route consisting of several roads, he considers the perishability of the route to be equal to the smallest perishability of all the roads in this route.

The government of Never has not yet decided where to build the museum, so they consider all n possible options. The most important is the sum of perishabilities of the routes to the museum city from all the other cities of Never, if the travelers strictly follow the directions of the signposts. The government of Never cares about their citizens, so they want to set the signposts in a way which minimizes this sum. Help them determine the minimum possible sum for all n possible options of the city where the museum can be built.

在“永不”国（Never），共有 $n$ 座城市，并拥有高度发达的公路系统。任意两座城市之间恰好有一条双向道路，因此道路总数高达 条！任意两条道路互不相交，且任何一条道路均不经过除其端点外的其他城市。“永不”国人已完全掌握了修建隧道与桥梁的技术。

一个独立委员会为“永不”国的每一条道路评估了一个正整数，称为该道路的易损性（perishability）。道路的易损性越低，驾车通行就越令人愉悦。

今年是“永不”国的交通年。政府决定在其中一座城市建造一座交通博物馆，并在其余每座城市中设置一块路标牌，指向某座城市（该城市不一定是博物馆所在城市）。这些路标牌必须满足如下关键条件：若任意一位居住在非博物馆城市的“永不”国人从其所在城市出发，并严格依照路标牌指示的方向持续行进，则此人最终必将抵达博物馆所在城市。

“永不”国人极其乐观。若某位“永不”国人沿由若干条道路组成的路径旅行，则他将该路径的易损性定义为该路径中所有道路的易损性的最小值。

目前，“永不”国政府尚未确定博物馆的建造地点，因此需考虑全部 $n$ 种可能的选址方案。最核心的指标是：当游客严格遵循路标牌指示前往博物馆所在城市时，从其余所有城市到博物馆城市的各条路径的易损性之和。由于政府心系国民福祉，他们希望以某种方式设置路标牌，使得该总和尽可能小。请你帮助政府计算：对博物馆可建造的全部 $n$ 座城市，分别求出该最小可能的总和。

The first line contains a single integer n (2 ≤ n ≤ 2000) — the number of cities in Never.

The following n - 1 lines contain the description of the road network. The i-th of these lines contains n - i integers. The j-th integer in the i-th line denotes the perishability of the road between cities i and i + j.

All road perishabilities are between 1 and 109, inclusive.

第一行包含一个整数 $n$（$2 \leq n \leq 2000$）—— 表示 Never 国的城市数量。

接下来的 $n-1$ 行描述道路网络。其中第 $i$ 行包含 $n-i$ 个整数。第 $i$ 行中的第 $j$ 个整数表示城市 $i$ 与城市 $i+j$ 之间道路的易腐性。

所有道路的易腐性均在 $1$ 到 $10^9$（含端点）之间。

For each city in order from 1 to n, output the minimum possible sum of perishabilities of the routes to this city from all the other cities of Never if the signposts are set in a way which minimizes this sum.

对于从 1 到 $n$ 的每个城市，输出在最优设置路标（即令该总和最小化）的情况下，从其余所有永世城（Never）城市到达该城市的路径的易腐性（perishability）之和的最小可能值。

The first example is explained by the picture below. From left to right, there is the initial road network and the optimal directions of the signposts in case the museum is built in city 1, 2 and 3, respectively. The museum city is represented by a blue circle, the directions of the signposts are represented by green arrows.

For instance, if the museum is built in city 3, then the signpost in city 1 must be directed to city 3, while the signpost in city 2 must be directed to city 1. Then the route from city 1 to city 3 will have perishability 2, while the route from city 2 to city 3 will have perishability 1. The sum of perishabilities of these routes is 3.

第一个示例由下图解释。从左到右，依次为初始道路网络，以及当博物馆分别建在城市 1、2 和 3 时，路标指示方向的最优方案。博物馆所在城市用蓝色圆圈表示，路标指示方向用绿色箭头表示。

例如，若博物馆建在城市 3，则城市 1 处的路标必须指向城市 3，而城市 2 处的路标必须指向城市 1。此时，从城市 1 到城市 3 的路径具有易损性 2，而从城市 2 到城市 3 的路径具有易损性 1。这些路径的易损性之和为 3。