题目理解

给定一个树，树的节点上有权值。对于每次操作，指定两节点 $u$ 和 $v$，我们需要从节点 $u$ 到节点 $v$ 的路径上，按路径的顺序给节点增加一定的权值。增加的权值是从 $x$ 开始，依次递增。

思路与方法

1. 路径计算

在树上，任意两点之间有且仅有一条简单路径。因此，我们首先需要能够高效地计算出两点之间的路径。这个问题的关键是如何快速找到路径，并在路径上更新权值。

题目内容

小美有一棵 $n$ 个结点的树，树上第 $i$ 个结点的权值为 $a_i$ 。

现在她定义树上任意两点 $u,v$ 的距离为 $dist(u,v)$ ，即树上两点间简单路径的边数。

现在她提出 $9$ 次操作，每次操作给定三个整数 $u,v,x$ ，她准备从 $u$ 出发，把 $u→v$ 简单路径上的结点权值，按节点在路径上出现的先后顺序，依次加上 $x,x+1,x+2,...,x+ dist(u,v)$ 。请你输出操作后所有结点的权值。

从节点 $u$ 到节点 $v$ 的简单路径定义为从节点 $u$ 出发，以节点 $v$ 为终点，随意在树上走，不经过重复的点和边走出来的序列。可以证明，在树上，任意两个节点间有且仅有一条简单路径。

输入描述

第一行两个整数 $n,q(2 ≤n,q≤ 10^5)$ ，表示树的结点总数和操作次数。

第二行 $n$ 个整数，第 $i$ 个整数 $a_i(1 ≤ a_i≤ 10^6)$ 表示树上第 $i$ 个结点的初始权值。

接下来 $n-1$ 行，每行两个整数 $u,v(1≤u,v≤n;u≠v)$ 表示 $u,v$ 之间存在一条无向边。

接下来 $q$ 行，每行三个整数 $u,v,x(1≤u,v≤n,1≤x≤10^6)$ 含义如题面所示。

输出描述

输出一行，共 $n$ 个整数，以空格隔开，表示操作后每个结点的权值。

样例1

输入

3 9
1 1 1
1 2
1 3
1 1 1
2 2 1
3 3 1
2 3 1
3 2 1
1 3 1
3 1 1
1 2 1
2 1 1

输出

12 9 9