11081108 SUSTech Online Judge
Problem 1108 --一个简单题

1108: 一个简单题

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 3  Solved: 3
[Submit][Status][Web Board]

Description

现在给一张无向带权图G(V, E), 我们假设对于每个点v,我们有一个点权值W(v), 对于每条边e, 我们有边权C(e), 现在你需要对每个点回答一个弱智问题, 问题的形式是这样的,对于每个点u, ans(u) = min_element(dist(u, v) + dist(v, u) + W(v)), 其中dist(u, v)是u到v的最短路.

Input

n <= 2 * 10 ^ 5, m <= 4 * 10 ^ 5

边权点权 1<=w <= 10^12。

单组数据,第一行给出V, E,代表图的点数和边数

接下来E行,每行有三个元素u, v, w,表示u-v之间有一条w价值的边

接下来一行V个数,代表每个点的点权 

Output

一行V个数,第i个代表ans(i).

Sample Input

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

Sample Output

12 10 12 

HINT

数据保证图联通,没有重边。

Source

 

[Submit][Status]