← 返回比赛

已结束【普及组】GESP“飞翔杯”第四届季度赛

← 上一题下一题 →

A5249 | $game$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

众所周知，Steam 在不同地区购买游戏，是有不同的价格的。小 Y 想找到购买某款开放世界冒险游戏最便宜的方案。 这款游戏在第 $i$ 个国家的售价为 $a_i$。总共有 $n$ 个国家，这 $n$ 个国家之间由 $m$ 条双向道路相连。每次经过第 $i$ 条道路需要付出 $w_i$ 的过路费。小 Y 购买游戏的花费是从自己所在的国家到购买游戏国家的 往返 过路费与购买游戏费用之和。 小 Y 很快就求出了从自己所在的国家该怎么买最便宜。但小 Y 心胸宽广，想计算出从每个国家出发，最小的购买游戏的花费分别是多少。

输入格式

第一行两个正整数 $n$ 和 $m$。 接下来 $m$ 行，每行三个正整数 $u, v, w$，表示有一条边连接国家 $u$ 和 $v$，且每经过一次需要付出的代价是 $w$。 接下来一行 $n$ 个数，第 $i$ 个数表示游戏在第 $i$ 个国家的售价 $a_i$。

输出格式

输出一行 $n$ 个数，第 $i$ 个数表示从第 $i$ 个国家出发，购买游戏的最小花费。

输入输出样例

输入 #1

输出 #1

6 14 1 25

C++ 编辑器

输入

输出