English · Original
Chinese · Translation
Formal · Original
Musicians of a popular band "Flayer" have announced that they are going to "make their exit" with a world tour. Of course, they will visit Berland as well.
There are _n_ cities in Berland. People can travel between cities using two-directional train routes; there are exactly _m_ routes, _i_\-th route can be used to go from city _v__i_ to city _u__i_ (and from _u__i_ to _v__i_), and it costs _w__i_ coins to use this route.
Each city will be visited by "Flayer", and the cost of the concert ticket in _i_\-th city is _a__i_ coins.
You have friends in every city of Berland, and they, knowing about your programming skills, asked you to calculate the minimum possible number of coins they have to pay to visit the concert. For every city _i_ you have to compute the minimum number of coins a person from city _i_ has to spend to travel to some city _j_ (or possibly stay in city _i_), attend a concert there, and return to city _i_ (if _j_ ≠ _i_).
Formally, for every you have to calculate , where _d_(_i_, _j_) is the minimum number of coins you have to spend to travel from city _i_ to city _j_. If there is no way to reach city _j_ from city _i_, then we consider _d_(_i_, _j_) to be infinitely large.
## Input
The first line contains two integers _n_ and _m_ (2 ≤ _n_ ≤ 2·105, 1 ≤ _m_ ≤ 2·105).
Then _m_ lines follow, _i_\-th contains three integers _v__i_, _u__i_ and _w__i_ (1 ≤ _v__i_, _u__i_ ≤ _n_, _v__i_ ≠ _u__i_, 1 ≤ _w__i_ ≤ 1012) denoting _i_\-th train route. There are no multiple train routes connecting the same pair of cities, that is, for each (_v_, _u_) neither extra (_v_, _u_) nor (_u_, _v_) present in input.
The next line contains _n_ integers _a_1, _a_2, ... _a__k_ (1 ≤ _a__i_ ≤ 1012) — price to attend the concert in _i_\-th city.
## Output
Print _n_ integers. _i_\-th of them must be equal to the minimum number of coins a person from city _i_ has to spend to travel to some city _j_ (or possibly stay in city _i_), attend a concert there, and return to city _i_ (if _j_ ≠ _i_).
[samples]
流行乐队 "Flayer" 宣布他们将举行一场世界巡演作为告别演出。当然，他们也会访问 Berland。
Berland 有 #cf_span[n] 座城市。人们可以使用双向火车路线在城市间旅行；共有恰好 #cf_span[m] 条路线，第 #cf_span[i] 条路线可以从城市 #cf_span[vi] 到达城市 #cf_span[ui]（反之亦然），使用这条路线需要花费 #cf_span[wi] 枚硬币。
每座城市都将被 "Flayer" 访问，第 #cf_span[i] 座城市的演唱会门票价格为 #cf_span[ai] 枚硬币。
你每个城市都有朋友，他们知道你的编程技能，请求你计算他们观看演唱会所需的最少硬币数。对于每座城市 #cf_span[i]，你需要计算：一个来自城市 #cf_span[i] 的人，必须花费的最少硬币数，以前往某座城市 #cf_span[j]（或可能留在城市 #cf_span[i]），观看那里的演唱会，然后返回城市 #cf_span[i]（若 #cf_span[j ≠ i]）。
形式上，对于每个 #cf_span[i]，你需要计算：#cf_span[min_{1 ≤ j ≤ n} (d(i, j) + a_j + d(j, i))]，其中 #cf_span[d(i, j)] 是从城市 #cf_span[i] 到城市 #cf_span[j] 所需的最少硬币数。如果无法从城市 #cf_span[i] 到达城市 #cf_span[j]，则我们认为 #cf_span[d(i, j)] 为无穷大。
第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[2 ≤ n ≤ 2·105], #cf_span[1 ≤ m ≤ 2·105])。
接下来 #cf_span[m] 行，第 #cf_span[i] 行包含三个整数 #cf_span[vi], #cf_span[ui] 和 #cf_span[wi] (#cf_span[1 ≤ vi, ui ≤ n, vi ≠ ui], #cf_span[1 ≤ wi ≤ 1012])，表示第 #cf_span[i] 条火车路线。不存在连接同一对城市的多重路线，即对于每对 #cf_span[(v, u)]，输入中不会同时出现额外的 #cf_span[(v, u)] 或 #cf_span[(u, v)]。
下一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ... an] (#cf_span[1 ≤ ai ≤ 1012]) —— 第 #cf_span[i] 座城市演唱会门票的价格。
请输出 #cf_span[n] 个整数。第 #cf_span[i] 个整数必须等于：来自城市 #cf_span[i] 的人，前往某座城市 #cf_span[j]（或可能留在城市 #cf_span[i]），观看演唱会并返回城市 #cf_span[i]（若 #cf_span[j ≠ i]）所需的最少硬币数。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[2 ≤ n ≤ 2·105], #cf_span[1 ≤ m ≤ 2·105])。接下来 #cf_span[m] 行，第 #cf_span[i] 行包含三个整数 #cf_span[vi], #cf_span[ui] 和 #cf_span[wi] (#cf_span[1 ≤ vi, ui ≤ n, vi ≠ ui], #cf_span[1 ≤ wi ≤ 1012])，表示第 #cf_span[i] 条火车路线。不存在连接同一对城市的多重路线，即对于每对 #cf_span[(v, u)]，输入中不会同时出现额外的 #cf_span[(v, u)] 或 #cf_span[(u, v)]。下一行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ... an] (#cf_span[1 ≤ ai ≤ 1012]) —— 第 #cf_span[i] 座城市演唱会门票的价格。
## Output
请输出 #cf_span[n] 个整数。第 #cf_span[i] 个整数必须等于：来自城市 #cf_span[i] 的人，前往某座城市 #cf_span[j]（或可能留在城市 #cf_span[i]），观看演唱会并返回城市 #cf_span[i]（若 #cf_span[j ≠ i]）所需的最少硬币数。
[samples]
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ denote the number of cities and train routes, respectively.
Let $ G = (V, E) $ be an undirected weighted graph with $ V = \{1, 2, \dots, n\} $ and $ E \subseteq V \times V $, where each edge $ (u, v) \in E $ has weight $ w(u, v) \in \mathbb{R}^+ $.
Let $ a_i \in \mathbb{R}^+ $ denote the concert ticket cost in city $ i $, for $ i \in V $.
Let $ d(i, j) $ denote the shortest path distance (minimum total weight) between cities $ i $ and $ j $ in $ G $; if no path exists, $ d(i, j) = \infty $.
**Constraints**
1. $ 2 \leq n \leq 2 \cdot 10^5 $
2. $ 1 \leq m \leq 2 \cdot 10^5 $
3. $ 1 \leq w(u, v) \leq 10^{12} $ for all $ (u, v) \in E $
4. $ 1 \leq a_i \leq 10^{12} $ for all $ i \in V $
5. Graph $ G $ is simple (no multiple edges or self-loops).
**Objective**
For each city $ i \in V $, compute:
$$
\min_{j \in V} \left( 2 \cdot d(i, j) + a_j \right)
$$
Output the result for each $ i = 1, 2, \dots, n $.
API Response (JSON)
{
"problem": {
"name": "D. Buy a Ticket",
"description": {
"content": "Musicians of a popular band \"Flayer\" have announced that they are going to \"make their exit\" with a world tour. Of course, they will visit Berland as well. There are _n_ cities in Berland. People can",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF938D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Musicians of a popular band \"Flayer\" have announced that they are going to \"make their exit\" with a world tour. Of course, they will visit Berland as well.\n\nThere are _n_ cities in Berland. People can...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "流行乐队 \"Flayer\" 宣布他们将举行一场世界巡演作为告别演出。当然，他们也会访问 Berland。\n\nBerland 有 #cf_span[n] 座城市。人们可以使用双向火车路线在城市间旅行；共有恰好 #cf_span[m] 条路线，第 #cf_span[i] 条路线可以从城市 #cf_span[vi] 到达城市 #cf_span[ui]（反之亦然），使用这条路线需要花费 #cf_span[...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of cities and train routes, respectively. \nLet $ G = (V, E) $ be an undirected weighted graph with $ V = \\{1, 2, \\dots, n\\} $ and $ E...",
"is_translate": false,
"language": "Formal"
}
]
}