Problem L
Lights, Camera, Airplane

Porco Rosso at Large

Porco Rosso is trying to catch the notorious air pirates, and he is trying to direct his underlings by lighting up the runway so they can take off. There are $N$ important locations on the runway, and there are $N-1$ lighted pathways between locations such that the runways form a tree rooted at location $1$ with every edge directed away from the root. Consider some location $p$ that has edges to $c_1, c_2, \ldots , c_k$. Then, location $p$ starts off with the edge from $p \rightarrow c_1$ illuminated. A plane starts at the root (location 1) and follows an illuminated path from the root to a location where it takes off. Planes only take off if there are no illuminated paths directed away from the current location. Every time a plane takes off, Porco Rosso doesn’t want to send another plane down the same path, so he flips a switch, causing every currently illuminated path to switch to the next edge $p \rightarrow c_{i+1}$. The currently illuminated path for $p$ returns back to the beginning $c_1$ if the cycle reaches the end.

Unfortunately, some of the lighted pathways are low on charge and they will lose battery before takeoff $t_i$. When a light is out of battery, Porco Rosso will still attempt to illuminate it, but no light will show, so no plane will travel along that edge.

Given the initial tree, the takeoffs when edges stop working, and the number of airplanes leaving, determine the number of times an airplane leaves from each important location.

Input

The first line of input is two space separated integers $N \: (1 \leq N \leq 100 \, 000)$ and $T \: (1 \leq T \leq 10^9)$ representing the number of important locations on the runway and the amount of takeoffs respectively.

The next $N$ lines will be of the form $k_i \; c_1 \; c_2 \ldots c_k$ where line $i$ represents that location $i$ has $k_i$ edges to locations $c_1, c_2, \ldots , c_k$ in that order. If location $i$ is a leaf node, $k_i$ will be $0$ and there will be no other input on that line. All locations are $1$-indexed.

The next $N-1$ lines will contain three space separated integers of the form $a_i \; b_i \; t_i \: (1 \leq a_i, b_i \leq N$ and $a_i \neq b_i)$, representing that the edge between locations $a_i$ and $b_i$ will lose power before takeoff $t_i$ ($1 \leq t_i \leq 10^9$). It is guaranteed that the edges given will satisfy the same tree structure described earlier in the input (including edges being guaranteed to have the same direction as specified earlier in the input).

Output

Output $N$ space separated integers $f_1 \; f_2 \; \ldots f_n$ where $f_i$ represents the number of times that a plane takes off from location $i$.

Sample Explanation

In the sample case, the order of take offs across the first 20 seconds is

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

3 7 4 2 3 1