题目描述

一家寿司餐厅中有 $N$ 张桌子，桌子之间由 $N-1$ 条双向传送带连接，任意两张桌子之间都直接或间接连通。因此，这些桌子和传送带构成一棵树。

对于每张桌子 $i$，给定它的邻桌数量 $K_i$，以及一个有序邻接表：

传送带按照如下唯一规则运输寿司：如果一份寿司刚从桌子 $V_{i,j}$ 来到桌子 $i$，那么它接下来会从桌子 $i$ 出发前往：

• $V_{i,j+1}$，若 $1\le j<K_i$；
• $V_{i,1}$，若 $j=K_i$。

此外，如果一份新寿司从桌子 $1$ 出发，前往 $V_{1,1}$，则它第一次到达任意桌子 $i$ 时，都是从 $V_{i,1}$ 来到 $i$。

Henry 和 Hetty 在时刻 $0$ 进入餐厅。餐厅中将陆续放上 $M$ 份寿司。第 $r$ 份寿司由三元组 $(x,y,t)$ 描述，表示它会在时刻 $t$ 被放在桌子 $x$ 处，并从桌子 $x$ 出发前往它有序邻接表中的第 $y$ 个邻桌 $V_{x,y}$。

一份寿司经过一条传送带需要 $1$ 个单位时间。如果 Henry 和 Hetty 坐在某张桌子 $i$，他们可以拿走所有经过桌子 $i$ 的寿司。

请对每张桌子 $i$，求出 Henry 和 Hetty 坐在该桌时，拿到全部 $M$ 份寿司所需等待到的最早时刻，即所有寿司第一次经过桌子 $i$ 的时间最大值。

输入格式

第一行包含两个整数 $N,M$，分别表示桌子数量和寿司数量。

接下来 $N$ 行描述每张桌子的有序邻接表。第 $i$ 行格式为：

K_i V_{i,1} V_{i,2} ... V_{i,K_i}

接下来 $M$ 行，每行包含三个整数 $x,y,t$，表示一份寿司在时刻 $t$ 放在桌子 $x$，并从 $x$ 出发前往 $V_{x,y}$。

输出格式

输出一行 $N$ 个整数，第 $i$ 个整数表示坐在桌子 $i$ 时拿到所有寿司所需等待到的最早时刻。

数据范围

• $1\le N\le 100000$；
• $1\le M\le 100000$；
• 对每个三元组 $(x,y,t)$，满足 $1\le x\le N$，$1\le y\le K_x$，$0\le t\le 100000$。

样例 1

输入

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

输出

1 4 0 2 7

解释

唯一一份寿司在时刻 $0$ 从桌子 $3$ 出发，前往桌子 $3$ 邻接表中的第 $1$ 张桌子，即桌子 $1$。

它的路线为：

3, 1, 4, 1, 2, 1, 3, 5, 3, ...

所以它第一次经过桌子 $1,2,3,4,5$ 的时间分别为 $1,4,0,2,7$。

样例 2

输入

3 2
2 2 3
1 1
1 1
2 1 0
3 1 1

输出

2 3 2