메트로

최근 강박성 장애 연구소는 여러 특이한 행동을 찾아내고 분류하는 일이 많아졌다. 당신은 일반 지하철 승객들 사이에서 보고된 이상한 강박 행동 하나를 조사하도록 파견되었다.

지하철에는 $N$개의 역이 있고, 이 역들은 $N-1$개의 양방향 경로로 연결되어 있다. 또한 고유 번호가 붙은 직선 경로의 노선이 $M$개 있다. 각 역에는 그 역을 지나는 노선 번호를 오름차순으로 보여 주는 전광판이 있다. 한 피실험자는 정수 리스트 $C_0, C_1, \ldots, C_L$을 보면 짝수 번째 항의 합 $S = C_0 + C_2 + C_4 + \cdots + C_{2K} + \cdots$을 계산하지 않고는 못 배긴다고 주장했다. 역마다 있는 전광판에는 이런 리스트가 하나씩 표시되어 있다.

$N$개 전광판 각각에 대해 이 합을 구하라.

첫 줄에 정수 $N$과 $M$이 주어진다. 이어지는 $N-1$개 줄에는 각각 정수 $x_i$, $y_i$가 주어지며, 역 $x_i$와 역 $y_i$가 직접 연결되어 있음을 뜻한다. 이어지는 $M$개 줄에는 각각 정수 $a_i$, $b_i$, $no_i$가 주어지며, 번호가 $no_i$인 노선이 역 $a_i$에서 역 $b_i$까지 운행한다는 뜻이다.

$N$줄을 출력한다. $i$번째 줄에는 역 $i$의 전광판에 대한 합을 한 수로 출력한다. 역 $i$를 지나는 노선이 하나도 없으면 0을 출력한다.

$1 \le N \le 200{,}000$, $1 \le M \le 200{,}000$, 모든 $i$에 대해 $1 \le no_i \le M$이다. 모든 역은 서로 도달할 수 있다.