题目背景

翻译自 CCO 的 2024P1题。

题目描述

有 $n$ 个岛屿通过 $m$ 条海路相连，每条路连接了两个岛屿 $a_i$ 和 $b_i$，需要花费 $c_i$ 个硬币。Perry 想要找到一条路径从他当前所在的岛屿出发，在旅途中开启宝箱并收集金币，并保证得到最大可能收益。事实证明，击退海怪的代价是相当昂贵的。为了寻找下一笔大的战利品，Perry 已经勘察了 $n$ 个岛屿，并确定第 $i$ 个岛屿上有一个装有 $v_i$ 枚硬币的宝箱。

他决定从岛屿 $X$ 开始，沿着一些的海上路线航行（可能不航行），最终到达岛屿 $Y$。在他的旅程结束时，他会在岛屿 $Y$ 打开箱子，收集战利品。

然而 Perry 不知道自己目前所在的岛屿！因此，对于每一个可能的起点岛屿 $X$，他都想知道从该岛屿出发的所有旅程中所能获得的最大可能的硬币数。你能帮助他计算这些值吗？你可以假设佩里有足够的硬币来穿越他选择的任何海上路线；他只关心下一次旅程的净收益。

输入格式

第一行两个整数 $n, m$。

第二行 $n$ 个整数 $v_i$。

往后 $m$ 行每行三个整数 $a_i, b_i, v_i$，其描述了一条海路 $i$。

保证无重边无自环。

输出格式

$n$ 行，每行一个整数，第 $i$ 行的整数代表以点 $i$ 为起点岛屿所获得的最大可能的硬币数。

4 5
6 5 9 2
1 2 0
3 2 3
4 3 6
1 3 5
2 4 2

6
6
9
4

提示

数据范围

对于 $100\%$ 的数据，$1 \le n \le 10^6$，$0 \le m \le 10^6$，$0 \le v_i,c_i \le 10^9$，$1 \le a_i,b_i \le n$。

样例解释 #1

对于第一个和第三个岛屿，最好待在岛上并打开岛上的箱子。

对于第二个岛屿，Perry 可以前往第一个岛屿并打开那里的箱子。这将带来 $6 - 0 = 6$ 枚硬币的净收益，是最佳的净收益。

对于第四个岛屿，Perry 可以前往第二个和第三个岛屿并打开那里的箱子。这将带来 $9 - 2 - 3 = 4$ 枚硬币的净收益，是最佳的净收益。