当林荫意识到他与女神 DJ 绝无可能时，林荫决定从她的世界中消失。
但是消失不代表离开，林荫决定在她看不到的地方成为一个隐形守护者。
林荫动用家族势力在全国范围内修建了 $N$ 座安全屋，其间由 $N-1$ 条协作物流通道连接成为一棵树。
林荫为此次行动准备了多种装备，分 $M$ 次运输。
每次林荫会在从 $X$ 到 $Y$ 的路径上每一座安全屋中放置一件编号为 $Z$ 的装备（$Z$ 为一个正整数）。
现在林荫想知道，$M$ 次运输后,每一座安全屋中哪种装备最多（如果有安全屋中没有装备则返回 $0$，如果有安全屋中装备最多的编号有多种，则返回装备最多的最小编号）。

第一行有两个正整数 $N$ 和 $M$。
第二行到第 $N$ 行：每行有两个正整数 $A$ 和 $B$，代表存 $A$ 与 $B$ 间存在一条协作物流道路。
第 $N+1$ 到第 $N+M$ 行：每行有三个正整数 $X,\ Y,\ Z$，代表从 $X$ 到 $Y$ 的所有安全屋各增加一件编号为 $Z$ 的装备。

一行 $N$ 个正整数，代表第 $i$ 座房屋中最多装备的编号。

对于 $30\%$ 的数据：$N \le 1000,\ M \le 10000$。
对于 $100\%$ 的数据：$M$ 以外的所有数字 $\le 10^5,\ M\le 5 \times 10^5$。