균형 발전

2062 대선에서 경곽당 정후가 경쟁자인 무소속 동현이를 제치고 대통령에 당선되었다.

정후는 자신의 공약인 지역 균형 발전을 위해 먼저 목표 지역을 트리 형태로 구성하였다. 엄선한 $N$개의 목표 지역을 정점으로 하고, 두 지역을 잇는 $N-1$개의 간선을 가지는 트리를 만들었다. 트리의 루트는 경기과학고등학교가 있는 지역 1이다.

다음으로 정후는 발전 계획, 즉 $N$개의 목표 지역의 활성화 순서를 나타내는 길이 $N$의 순열 $T$를 세웠다. 현재 시각은 0이며, 시각 $i$가 되면 지역 $T_i$를 활성화한다. 이 과정에서 계획에 없던 활성화가 일어날 수도 있는데, 지역의 누적 유입 인구가 $C_i$ 이상이 될 때이다. 지역의 누적 유입 인구는 처음에 0이다.

계획에 있든 없든, 지역 $i$가 활성화되면 즉시 거리가 $R_i$ 이하인 자손 지역 모두, 즉 지역 $i$를 조상으로 가지면서 지역 $i$까지의 거리가 $R_i$ 이하인 지역 모두에 $X_i$만큼의 인구 이동이 일어난다. 즉, 거리가 $R_i$ 이하인 자식 지역 모두의 누적 유입 인구가 $X_i$만큼 증가한다. 활성화가 연쇄적으로 일어날 수도 있으며, 연쇄 활성화의 순서가 여러 가지일 때에는 아무 순서로 활성화가 일어난다.

정후가 발전 계획을 살펴볼 수 있도록 각 지역이 활성화되는 시각을 구하라.

첫째 줄에 정수 $N$이 주어진다. 둘째 줄부터 $N-1$개의 줄에 걸쳐 세 정수 $u_i$, $v_i$, $w_i$가 공백으로 구분되어 주어진다. 이는 지역 $u_i$와 지역 $v_i$가 거리 $w_i$의 길로 연결되어 있음을 의미한다. 다음 줄에는 $N$개의 정수 $T_i$가 공백으로 구분되어 주어진다. 이어서 $N$개의 줄에 걸쳐 $i$째 줄에 세 정수 $C_i$, $R_i$, $X_i$가 공백으로 구분되어 주어진다.

각 지역이 활성화되는 시각을 차례로 공백으로 구분하여 한 줄에 $N$개의 정수로 출력한다.

• $1 \le N \le 200000$
• $1 \le T_i \le N$
• $i \ne j$이면 $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$
• 중복 간선이 없다.
• 주어지는 모든 수는 정수이다.
• 목표 지역은 트리 형태이다.