海盗佩里正在航行于七海之上！他拥有一张地图，上面有 $N$ 座岛屿，由 $M$ 条海上航线连接。第 $i$ 条航线连接岛屿 $a_i$ 和 $b_i$，双向通行的费用均为 $c_i$ 枚金币。事实证明，击退海怪的费用可能相当昂贵。为了寻找下一次大掠夺，佩里侦察了 $N$ 座岛屿中的每一座，并确定第 $i$ 座岛屿上有一个装有 $v_i$ 枚金币的宝箱。
他现在需要规划下一次旅程。他决定从岛屿 $x$ 出发，沿着某条（可能为空的）航线路径航行，最终到达岛屿 $y$。旅程结束时，他会打开岛屿 $y$ 上的宝箱并收集他应得的战利品。
但有一个小问题：佩里不知道他目前身处哪座岛屿！因此，对于每一个可能的起始岛屿 $x$，他都想知道从岛屿 $x$ 出发的所有旅程中，他能获得的最大金币数量。你能帮他计算这些值吗？你可以假设佩里有足够的金币来遍历他选择的任何航线路径；他只关心下一次旅程的净利润。
输入格式
第一行包含两个空格分隔的整数 $N$ 和 $M$。
第二行包含 $N$ 个空格分隔的整数 $v_1, v_2, \dots, v_N$ ($0 \le v_i \le 10^9$)。
接下来的 $M$ 行，每行包含三个空格分隔的整数 $a_i, b_i$ ($1 \le a_i, b_i \le N$) 和 $c_i$ ($0 \le c_i \le 10^9$)。
保证任意两座岛屿之间最多只有一条航线，且每条航线连接两座不同的岛屿。
子任务
| 分值 | $N$ 的范围 | $M$ 的范围 | 附加约束 |
|---|---|---|---|
| 5 分 | $1 \le N \le 3\,000$ | $0 \le M \le 3\,000$ | 无 |
| 5 分 | $1 \le N \le 10^6$ | $0 \le M \le 10^6$ | 对于所有 $i$，满足 $c_i = 0$ 或 $c_i = 10^9$ |
| 7 分 | $1 \le N \le 10^6$ | $0 \le M \le 10^6$ | 任意两座岛屿之间恰好有一条路径 |
| 8 分 | $1 \le N \le 10^6$ | $0 \le M \le 10^6$ | 无 |
输出格式
输出 $N$ 行，其中第 $x$ 行包含从岛屿 $x$ 出发的任何旅程所能获得的最大净利润（以金币为单位）。
样例
输入 1
4 5 6 5 9 2 1 2 0 3 2 3 4 3 6 1 3 5 2 4 2
输出 1
6 6 9 4
说明
对于第一座和第三座岛屿，最好的选择是留在原地并打开岛屿本身的宝箱。
对于第二座岛屿，佩里可以航行到第一座岛屿并打开那里的宝箱。这带来的净利润为 $6 - 0 = 6$ 枚金币，这是可能的最大净利润。
对于第四座岛屿，佩里可以航行到第二座岛屿，然后再到第三座岛屿，并打开那里的宝箱。这带来的净利润为 $9 - 2 - 3 = 4$ 枚金币，这是可能的最大净利润。