题目描述

译自 CCO 2024 Day1 T1「Treasure Hunt」。

佩里船长扬帆起航，在浩瀚的七海中冒险！他有一张藏宝图，上面标注了 $N$ 个岛屿，这些岛屿由 $M$ 条航线连接起来。第 $i$ 条航线连接着编号为 $a_i$ 和 $b_i$ 的岛屿，航行这条路线（无论哪个方向）都需要花费 $c_i$ 个金币。看来，跟海怪搏斗可是一笔不小的开销啊！为了找到他的下一个大宝藏，佩里仔细勘察了这 $N$ 个岛屿，并确定了第 $i$ 个岛屿藏有价值 $v_i$ 个金币的宝箱。

现在，他需要计划好接下来的航程。佩里决定从岛屿 $x$ 出发，沿着一些航线（可能为空）航行，最后到达岛屿 $y$。到达目的地后，他将打开岛屿 $y$ 上的宝箱，收取应得的战利品。

但有一个小问题：佩里迷失方向了，他不知道自己现在身在哪个岛屿！因此，对于每一个可能的出发岛屿 $x$，他都想知道从该岛屿出发的所有航程中，他能赚到的最大金币数。假设佩里有很多金币，可以支付任何航线的通行费；他只关心航程的净收益（到达目的地的宝藏价值减去航行花费）。

输入格式

第一行包含两个用空格隔开的整数 $N$ 和 $M$，分别表示岛屿数量和航线数量。

第二行包含 $N$ 个用空格隔开的整数 $v_1, v_2, \ldots, v_N\ (0 \leq v_i \leq 10^9)$，表示每个岛屿的宝藏价值。

接下来的 $M$ 行，每行包含三个用空格隔开的整数 $a_i$, $b_i\ (1 \leq a_i, b_i \leq N)$ 和 $c_i\ (0 \leq c_i \leq 10^9)$，分别表示第 $i$ 条航线连接的两个岛屿编号以及航行花费。

保证任何两座岛屿之间最多只有一条航线，并且每条航线连接的都是不同的岛屿。

输出格式

输出 $N$ 行，第 $x$ 行表示从岛屿 $x$ 出发所能获得的最大净收益（金币数）。

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

对于第一个和第三个岛屿来说，最好的选择就是待在原地，直接打开岛上的宝箱。

对于第二个岛屿，佩里可以航行到第一个岛屿并打开那里的宝箱。这样可以获得 $6 - 0 = 6$ 个金币的净收益，这也是他能获得的最大净收益。

对于第四个岛屿，佩里可以依次航行到第二个和第三个岛屿，然后打开第三个岛屿的宝箱。这样可以获得 $9 - 2 - 3 = 4$ 个金币的净收益，这也是他能获得的最大净收益。

数据范围与提示