{"problem":{"name":"D. Perishable Roads","description":{"content":"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 int","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF806D"},"statements":[{"statement_type":"Markdown","content":"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.\n\nAn 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.\n\nIt'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.\n\nNeverians 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.\n\nThe 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.\n\n## Input\n\nThe first line contains a single integer _n_ (2 ≤ _n_ ≤ 2000) — the number of cities in Never.\n\nThe 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_.\n\nAll road perishabilities are between 1 and 109, inclusive.\n\n## Output\n\nFor 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.\n\n[samples]\n\n## Note\n\nThe 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.\n\nFor 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.\n\n<center>![image](https://espresso.codeforces.com/27d3608236ddddddce1675789a01a3aacdb4b0cf.png)</center>","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"[{\"iden\":\"statement\",\"content\":\"在Never国，有#cf_span[n]座城市和一个发达的公路系统。每对城市之间恰好有一条双向公路，因此总共有#cf_span[\\\\frac{n(n-1)}{2}]条公路！没有任何两条公路相交，也没有任何公路经过中间城市。Never人已经掌握了建造隧道和桥梁的技艺。\\n\\n一个独立委员会为每条公路评估了一个正整数，称为该公路的#cf_span(class=[tex-font-style-underline], body=[perishability])。公路的perishability越低，驾驶通过该公路就越愉快。\\n\\n今年是Never的交通年。决定在其中一座城市建造一座交通博物馆，并在其他每个城市设置一个指路牌，指向某个城市（不一定就是博物馆所在的城市）。这些指路牌必须满足以下重要条件：如果任何居住在没有博物馆的城市的Never人从该城市出发，沿着指路牌的方向旅行，那么他最终将到达博物馆所在的城市。\\n\\nNever人极其乐观。如果一个Never人沿着由多条公路组成的路线旅行，他将该路线的#cf_span(class=[tex-font-style-underline], body=[perishability of the route])定义为该路线中所有公路的perishability的最小值。\\n\\nNever政府尚未决定在何处建造博物馆，因此他们考虑所有#cf_span[n]种可能的选项。最重要的是，当旅行者严格遵循指路牌方向时，从所有其他城市到博物馆所在城市的路线的perishability之和。政府关心其公民，因此希望以最小化该总和的方式设置指路牌。请帮助他们确定，当博物馆建在每一个可能的城市时，该总和的最小可能值。\\n\\n第一行包含一个整数#cf_span[n]（#cf_span[2 ≤ n ≤ 2000]）——Never国的城市数量。\\n\\n接下来的#cf_span[n - 1]行描述了公路网络。第#cf_span[i]行包含#cf_span[n - i]个整数。第#cf_span[i]行中的第#cf_span[j]个整数表示城市#cf_span[i]与城市#cf_span[i + j]之间公路的perishability。\\n\\n所有公路的perishability都在#cf_span[1]到#cf_span[10^9]之间（包含端点）。\\n\\n请按城市编号从1到#cf_span[n]的顺序，输出当博物馆建在该城市时，从所有其他城市到该城市的路线的perishability之和的最小可能值（指路牌设置方式需使该和最小）。\\n\\n第一个示例由下图解释。从左到右，分别是初始公路网络，以及当博物馆分别建在城市1、2和3时指路牌的最优方向。博物馆所在城市用蓝色圆圈表示，指路牌方向用绿色箭头表示。\\n\\n例如，如果博物馆建在城市3，则城市1的指路牌必须指向城市3，而城市2的指路牌必须指向城市1。那么从城市1到城市3的路线的perishability为2，从城市2到城市3的路线的perishability为1。这两条路线的perishability之和为3。\"},{\"iden\":\"input\",\"content\":\"第一行包含一个整数#cf_span[n]（#cf_span[2 ≤ n ≤ 2000]）——Never国的城市数量。接下来的#cf_span[n - 1]行描述了公路网络。第#cf_span[i]行包含#cf_span[n - i]个整数。第#cf_span[i]行中的第#cf_span[j]个整数表示城市#cf_span[i]与城市#cf_span[i + j]之间公路的perishability。所有公路的perishability都在#cf_span[1]到#cf_span[10^9]之间（包含端点）。\"},{\"iden\":\"output\",\"content\":\"请按城市编号从1到#cf_span[n]的顺序，输出当博物馆建在该城市时，从所有其他城市到该城市的路线的perishability之和的最小可能值（指路牌设置方式需使该和最小）。\"},{\"iden\":\"examples\",\"content\":\"输入31 23输出223输入62 9 9 6 67 1 9 109 2 54 108输出6575711\"},{\"iden\":\"note\",\"content\":\"第一个示例由下图解释。从左到右，分别是初始公路网络，以及当博物馆分别建在城市1、2和3时指路牌的最优方向。博物馆所在城市用蓝色圆圈表示，指路牌方向用绿色箭头表示。例如，如果博物馆建在城市3，则城市1的指路牌必须指向城市3，而城市2的指路牌必须指向城市1。那么从城市1到城市3的路线的perishability为2，从城市2到城市3的路线的perishability为1。这两条路线的perishability之和为3。  \"}]}","is_translate":true,"language":"Chinese"}],"meta":{"iden":"CF806D","tags":["graphs","shortest paths"],"sample_group":[["3\n1 2\n3","2\n2\n3"],["6\n2 9 9 6 6\n7 1 9 10\n9 2 5\n4 10\n8","6\n5\n7\n5\n7\n11"]],"created_at":"2026-03-03 11:00:39"}}