红猪（Porco Rosso）正试图抓捕臭名昭著的空中海盗，他试图通过点亮跑道来指引部下，以便他们能够起飞。跑道上有 $N$ 个重要位置，位置之间有 $N - 1$ 条亮起的通道，使得跑道形成一棵以位置 1 为根的树，所有边都从根节点指向外。

考虑某个位置 $p$，它有指向 $c_1, c_2, \dots, c_k$ 的边。初始时，位置 $p$ 指向 $c_1$ 的边 $p \to c_1$ 是亮起的。一架飞机从根节点（位置 1）出发，沿着亮起的路径从根节点行驶到某个位置并起飞。只有当当前位置没有向外的亮起路径时，飞机才会起飞。每次有飞机起飞时，红猪不想让另一架飞机走相同的路径，因此他会拨动开关，使所有当前亮起的路径切换到下一条边 $p \to c_{i+1}$。如果循环到达末尾，位置 $p$ 当前亮起的路径将返回到最开始的 $c_1$。

红猪逍遥法外

不幸的是，一些亮起的通道电量不足，它们会在第 $t_i$ 次起飞前失去电力。当某个灯没电时，红猪仍会尝试点亮它，但不会有光亮显示，因此没有飞机能沿着该边行驶。

给定初始的树、各边停止工作时的起飞次数，以及出发的飞机总数，求每架飞机从各个重要位置起飞的次数。

输入格式

输入的第一行包含两个空格分隔的整数 $N$ ($1 \le N \le 100\,000$) 和 $T$ ($1 \le T \le 10^9$)，分别代表跑道上重要位置的数量和起飞的总次数。

接下来的 $N$ 行格式为 $k_i\ c_1\ c_2\ \dots\ c_k$，其中第 $i$ 行表示位置 $i$ 依次有 $k_i$ 条指向位置 $c_1, c_2, \dots, c_k$ 的边。如果位置 $i$ 是叶子节点，则 $k_i$ 为 0，且该行没有其他输入。所有位置均从 1 开始编号。

接下来的 $N - 1$ 行，每行包含三个空格分隔的整数 $a_i\ b_i\ t_i$ ($1 \le a_i, b_i \le N$ 且 $a_i \ne b_i$)，表示位置 $a_i$ 和 $b_i$ 之间的边将在第 $t_i$ 次起飞前失去电力 ($1 \le t_i \le 10^9$)。保证给出的边符合前文输入中描述的树形结构（包括保证边的方向与前文指定的方向一致）。

输出格式

输出 $N$ 个空格分隔的整数 $f_1\ f_2\ \dots\ f_n$，其中 $f_i$ 表示飞机从位置 $i$ 起飞的次数。

样例

输入样例 1

6 20
2 2 3
0
3 4 5 6
0
0
0
1 2 15
1 3 25
3 4 12
3 5 17
3 6 7

输出样例 1

3 7 4 2 3 1

说明

在样例中，前 20 秒内的起飞顺序为：

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