You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

吞噬变异

题目描述

开局一只鲲，进化全靠吞！

游戏中有 $n$ 种异兽，系统售价为 $a_i$。游戏中有吞噬系统，吞噬规则的形式为 (x, y) -> z：

• 让一只种类为 $x$ 的异兽吃掉一只种类为 $y$ 的异兽，变异出一只种类为 $z$ 的异兽，而参与吞噬的两只异兽消失；

游戏中有 $m$ 种不同的吞噬形式，已知每种吞噬规则的 $x, y, z$。

在每个回合，你可以进行2种操作：

1. 花费 $a_i$ 购买一只种类为 $i$ 的异兽；
2. 按照某种吞噬规则进行一次吞噬变异（需要保证吞噬所需的2只异兽已经准备好）；

请你求出得到每种异兽所需要的最小总花费。

输入格式

• 第一行两个整数 $n, m$
• 第二行 $n$ 个整数 $a_1, a_2, ..., a_n$ 表示初始价格
• 接下来 $m$ 行，每行3个整数 $x, y, z$，代表一个吞噬规则（保证 $x, y, z$ 互不相同）

输出格式

• 输出一行 $n$ 个整数，代表得到第 $i$ 只异兽的最小总花费

样例

样例1输入

7 3 6 10 3 2 2 3 100 1 2 7 4 5 1 3 6 2

样例1输出

4 6 3 2 2 3 10

样例2输入

10 5 1 4 5 4 15 14 16 15 19 20 1 3 6 2 6 7 5 8 8 6 8 9 9 9 10

样例2输出

1 4 5 4 15 6 10 15 19 20

数据范围

• 对于30%的数据，$n \leq 10$
• 对于60%的数据，$n \leq 100$
• 对于100%的数据，$n \leq 10^5, m \leq 2 \times 10^5$