Background

《星战》结束后，战时用于《数据传输》的 Y 镇开放了旅游。

Description

Y 镇有 \(n\) 户人家，由 \(n-1\) 条双向道路连通。在接下来的一天内，将会有 \(m\) 个景点开放。对于第 \(i\) 个景点，只有 \(u_i\) 到 \(v_i\) 路径上的居民可以游览，且推荐指数为 \(a_i\)。第 \(j\) 户人家在当天最多可以游览 \(k_j\) 个景点。设某户人家的一个旅游方案依次去了 \(x\) 个各不相同的景点 \(i_1,i_2,...,i_x\)，则定义这个旅游方案的开心指数为 \(\sum_{j=1}^{x}{j\times a_{i_j}}\)。小 Y 将会为每户人家制定一份开心指数最大的《假期计划》，由于他忙着玩《策略游戏》，请你帮助他完成这个并不艰巨的任务。

Format

Input

第一行两个正整数 \(n,m\)。
第二行 \(n\) 个正整数，第 \(i\) 个数表示 \(k_i\)，即第 \(i\) 户人家最多可游览的景点个数。
接下来 \(n-1\) 行，每行两个正整数 \(x,y\) 表示树上的一条边。
接下来 \(m\) 行，每行三个正整数 \(u,v,a\) 描述一个景点。

Output

输出共 \(n\) 行，第 \(i\) 行一个非负整数表示第 \(i\) 户人家最大的开心指数。

Sample 1

Input

5 5
3 2 2 1 3
1 2
1 3
3 4
3 5
1 3 1
2 4 2
2 5 3
1 5 4
4 5 5

Output

20
8
14
5
26

Limitation

测试点编号	\(n\le\)	\(m\le\)	特殊性质
1-3	1000	1000	无
4-6	\(10^5\)	\(10^5\)	树随机生成
7-9	\(10^5\)	\(10^5\)	\(a_i\le 10\)
10-12	\(10^5\)	\(10^5\)	树是一条链
13-15	\(10^5\)	\(10^5\)	\(u_i=1\)
16-20	\(10^5\)	\(10^5\)	无

对于 100% 的数据：

\(1\le n,m\le 10^5\)

\(1\le a_i\le 10^5\)

\(1\le k_j\le m\)

\(1\le u_i,v_i\le n\) 且 \(u,v\) 不相同

\(1\le x,y\le n\)