CF938D Buy a Ticket

著名乐队“Flayer”的成员宣布他们将以一次世界巡演“谢幕”。当然，他们也会访问 Berland。 Berland 有 $n$ 个城市。人们可以通过双向火车线路在城市之间旅行；共有 $m$ 条线路，第 $i$ 条线路可以从城市 $v_{i}$ 到城市 $u_{i}$（也可以从 $u_{i}$ 到 $v_{i}$），使用这条线路需要 $w_{i}$ 个金币。 每个城市都会举办“Flayer”的演唱会，第 $i$ 个城市的演唱会门票价格为 $a_{i}$ 个金币。 你在 Berland 的每个城市都有朋友，他们知道你的编程能力后，请你帮忙计算他们去听演唱会所需支付的最少金币数。对于每个城市 $i$，你需要计算一个人从城市 $i$ 出发，前往某个城市 $j$（也可以留在城市 $i$），在那里参加演唱会，然后返回城市 $i$（如果 $j \neq i$），所需支付的最少金币数。 形式化地，对于每个 $i$，你需要计算 $\min_{j=1}^{n} \left( d(i, j) + a_j + d(j, i) \right)$，其中 $d(i, j)$ 表示从城市 $i$ 到城市 $j$ 的最少花费。如果无法从城市 $i$ 到达城市 $j$，则认为 $d(i, j)$ 是无穷大。

第一行包含两个整数 $n$ 和 $m$（$2 \leq n \leq 2 \cdot 10^{5}$，$1 \leq m \leq 2 \cdot 10^{5}$）。 接下来 $m$ 行，每行包含三个整数 $v_{i}$、$u_{i}$ 和 $w_{i}$（$1 \leq v_{i}, u_{i} \leq n, v_{i} \neq u_{i}$，$1 \leq w_{i} \leq 10^{12}$），表示第 $i$ 条火车线路。不存在连接同一对城市的多条线路，即对于每对 $(v, u)$，输入中不会出现额外的 $(v, u)$ 或 $(u, v)$。 接下来一行包含 $n$ 个整数 $a_{1}, a_{2}, \ldots, a_{n}$（$1 \leq a_{i} \leq 10^{12}$），表示在第 $i$ 个城市参加演唱会的门票价格。

输出 $n$ 个整数，第 $i$ 个表示一个人从城市 $i$ 出发，前往某个城市 $j$（也可以留在城市 $i$），在那里参加演唱会，然后返回城市 $i$（如果 $j \neq i$），所需支付的最少金币数。

由 ChatGPT 4.1 翻译