Balanced Development

In the 2062 presidential election, Kyeonggwak-dang Jeong-hu won the presidency by defeating Dong-hyeon, an independent candidate.

For his balanced regional development pledge, Jeong-hu first built a tree of target regions. The tree has $N$ carefully chosen target regions as vertices and $N-1$ edges, each connecting two regions. Region 1, where Gyeonggi Science High School is located, is the root.

Next, Jeong-hu drew up a development plan, which is a permutation $T$ of length $N$ that gives the activation order of the $N$ target regions. The current time is 0, and at time $i$, region $T_i$ is activated. During this process, an activation not in the plan can occur when a region's cumulative inflow population reaches $C_i$ or more. The cumulative inflow population of every region starts at 0.

Whether or not it is in the plan, when region $i$ is activated, a population movement of $X_i$ immediately occurs in every descendant region within distance $R_i$, that is, every region that has $i$ as an ancestor and lies at distance $R_i$ or less from $i$. In other words, the cumulative inflow population of every child region within distance $R_i$ increases by $X_i$. Activations can chain. When several chain activation orders are possible, activations happen in any one of those orders.

Find the activation time of each region to help Jeong-hu review the development plan.

The first line contains an integer $N$. Each of the next $N-1$ lines contains three integers $u_i$, $v_i$, $w_i$, meaning regions $u_i$ and $v_i$ are connected by a road of length $w_i$. The next line contains $N$ integers $T_i$, separated by spaces. Each of the next $N$ lines contains three integers $C_i$, $R_i$, $X_i$, separated by spaces, with the $i$-th of these lines describing region $i$.

Print $N$ integers on a single line, separated by spaces, giving the activation time of each region in order.

• $1 \le N \le 200000$
• $1 \le T_i \le N$
• If $i \ne j$, then $T_i \ne T_j$.
• $0 \le R_i \le 10^{15}$
• $1 \le C_i \le 10^{15}$
• $1 \le X_i, w_i \le 10^{9}$
• $1 \le u_i, v_i \le N$, $u_i \ne v_i$
• There are no duplicate edges.
• All given numbers are integers.
• The target regions form a tree.