题目描述

游戏中有 $n$ 种异兽，售价 $p[1...n]$。有 $m$ 种吞噬规则 $(a,b,c)$：

• 种类 $a$ 的异兽吃掉种类 $b$ 的异兽，变异出种类 $c$ 的异兽（$a$,$b$ 消失）
  操作包括：购买异兽或进行吞噬变异。求得到每只异兽的最小总花费。

输入格式

• 第一行 2 个整数 $n、m$
• 第二行 n 个整数 $p[1...n]$
• 接下来 m 行，每行 3 个整数 $a,b,c$（保证 $a≤b$）

输出格式

• 一行 $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,m ≤ 10$
• 60% 数据：$n,m ≤ 10^3$
• 100% 数据：$1 ≤ n,m ≤ 10^5$, $1 ≤ p[i] ≤ 10^6$