← 返回题目列表

Codeforces · 938/D

D. 买票

中文机器翻译题面 查看原题

流行乐队“Flayer”的音乐家宣布他们将通过世界巡演“退出”。当然,他们也会访问贝尔兰。

Berland 有 n 个城市。人们可以使用双向火车路线在城市之间出行;正好有m条路线,第i条路线可用于从城市vi到城市ui(以及从ui到vi),使用这条路线需要花费wi币。

每个城市都会有“剥皮者”访问,第i个城市的演唱会门票费用为ai币。

你在伯兰的每个城市都有朋友,他们了解你的编程技巧,要求你计算他们参观音乐会所需支付的最低可能数量的硬币。对于每个城市 i,您必须计算来自城市 i 的人前往某个城市 j(或可能留在城市 i)、参加那里的音乐会,然后返回城市 i(如果 j ≠ i)所需花费的最少硬币数量。

正式来说,对于 [1,n]$$ 中的每个 $$i \in,您必须计算 $$\min_{j=1}^{n} 2d(i,j) + a_j$$,其中 d(i, j) 是从城市 i 到城市 j 所需花费的最少硬币数量。如果没有办法从城市 i 到达城市 j,那么我们认为 d(i, j) 无限大。

输入

第一行包含两个整数 n 和 m (2 ≤ n ≤ 2·105, 1 ≤ m ≤ 2·105)。

接下来是 m 行,第 i 行包含三个整数 vi、ui 和 wi (1 ≤ vi, ui ≤ n, vi ≠ ui, 1 ≤ wi ≤ 1012),表示第 i 条火车路线。不存在连接同一对城市的多条火车路线,也就是说,对于每个 (v, u),输入中既不存在额外的 (v, u) 也不存在 (u, v)。

下一行包含 n 个整数 a1, a2, ... ak (1 ≤ ai ≤ 1012) — 在第 i 个城市参加音乐会的价格。

输出

打印 n 个整数。其中第 i 个必须等于来自城市 i 的人前往某个城市 j(或可能留在城市 i)、在那里参加音乐会并返回城市 i(如果 j ≠ i)所需花费的最小硬币数量。

示例

输入 #1

4 2
1 2 4
2 3 7
6 20 1 25

输出 #1

6 14 1 25

输入 #2

3 3
1 2 1
2 3 1
1 3 1
30 10 20

输出 #2

12 10 12