吞噬变异

题目描述

开局一只鲲，进化全靠吞！ 游戏中有$N$种异兽，系统售价为$p[1,,,N]$。游戏中有吞噬系统，吞噬规则的形式为$(a,b,c)$： 让一只种类$a$的异兽吃掉一只种类为$b$的异兽，变异出一只种类为$c$的异兽，而参与吞噬的$a,b$类的两只异兽消失； 游戏中有$m$种不同的吞噬形式，已知每种吞噬规则的$(a,b,c)$。 在每个回合，你可以进行2种操作： 花费$p[i]$购买一只$i$种类的异兽； 按照某种吞噬规则进行一次吞噬变异（需要保证吞噬所需的2只异兽已经准备好）； 请你求出得到每只异兽所需要的最小总花费

Format

输入格式

第一行2个整数 $n,m$ 第二行n个整数 $p[1...n]$ 接下来$m$行每行3个整数$a,b,c$，代表一个吞噬规则（保证$a \leq b$且互不相同 ）。

输出格式

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

样例

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

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

4 6 3 2 2 3 10

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

1 4 5 4 15 6 10 15 19 20

样例3

见下发样例

数据范围

对于30%的数据，$n,m \leq 10$ 对于60%的数据，$n,m \leq 10^{3}$ 对于100%的数据，$1 \leq n,m \leq 10^{5}$,$1 \leq p[i] \leq 10^{6}$,$1 \leq a \leq b \leq n$, $1 \leq c \leq n$