该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

石老板在上课时突然晕倒了，十万火急，你必须解出这道题，然后抢救石老板......

给定 $n$ 个节点的一棵树，同时给定 $m$ 条树上路径，每条路径带有一个权值 $w_i$。

同时树的 $n - 1$ 条边按照输入的顺序从 $1$ 到 $n - 1$ 标号。

现在规定记 $S_u$ 表示不包含第 $u$ 条树边的且属于给定的 $m$ 条路径的路径集合。

对于 $\forall$ $u \in[1,n - 1]$ ，求如下的答案：$\displaystyle \operatorname{mex}_{i \in S_u} w_i$

自然语言解释为：对于每一条树边求 $m$ 条路径中不经过它的路径的权值集合的 $\operatorname{mex}$

这里的 $\operatorname{mex}$ 指的是最小的没有出现的正整数。

同时并不保证所有的路径不重复，也就是可能对于同一组 $u,v$ 会有多组路径！

可能存在 $u = v$，这样的路径不包含任何树边。

输入格式

第一行 $n,m$ 意义如上。

接下来 $n - 1$ 行每行给出 $u,v$ 表示 $u,v$ 之间有一条边。

再接下来 $m$ 行每行给出 $s,t,w$ 表示有一条从树上 $s$ 号点到 $t$ 号点的权值为 $w$ 的简单路径。

ps. 简单路径指的是没有环的路径。

输出格式

$n - 1$ 行，第 $i$ 行对应不经过第 $i$ 条边的答案

样例

输入样例

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

输出样例

1
2
3
3

ex_treemex2.in/ex_treemex2.ans​ 对应下面 $20\%$ 数据的部分。

ex_treemex3.in/ex_treemex3.ans 对应下面另外 $28\%$ 数据的部分。

样例下载

数据范围

存在 $20\%$ 的数据满足 $1 \leq n,m\leq 3000$

存在另外 $28 \%$ 的数据保证 ： 形成的树是一条链，并且链的一端是 $1$ 号节点。

对于 $80 \%$ 的数据保证 ： $1 \leq n,m\leq 10^5$

对于 $100 \%$ 的数据保证 ： $1\le n \leq 5 \times 10^5, m \leq 2\times 10 ^ 6,1 \leq w_i \leq m$