原题链接

CF938D - Buy a Ticket

1. 做完后记得选择这个选择题。 {{ select(1) }}

• 提交并且通过了
• 还没有提交，或者提交了 WA 了。

题目描述

流行乐队 Flayer 将在 $n$ 个城市开演唱会，这 $n$ 个城市的人都想去听演唱会。每个城市的票价不同，于是这些人就想是否能去其他城市听演唱会更便宜（去要路费的，而且需要返程，可以描述为

也就是说你需要给每个城市的人都找到去哪个城市观看演唱会的代价最小，假如城市 $i$ 的人前往城市 $j$ 观看演唱会，这个代价包括去的城市的演唱会门票 $a_j$ 以及来回的最短路 $2*d(i,j)$

输入格式

第一行输入两个整数 $n,m$ 其中 $2\leq n\leq 2*10^5,1\leq m\leq 2*10^5$

接下来 $m$ 行每行三个整数分别为 $v_{i}$ , $u_{i}$ 以及 $w_{i}$ ( $1<=v_{i},u_{i}<=n,v_{i}≠u_{i}$ , $1<=w_{i}<=10^{12}$ )

最后一行包括 $n$ 个整数 $a_{1},a_{2},...\ a_{k}$ ( $1<=a_{i}<=10^{12}$ ) — 含义是到每个城市看演唱会的价格

输出格式

输出一共输出 $n$ 行，含义为到第 $i$ 个城市的人观看演唱会的最小花费。

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

6 14 1 25

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

12 10 12