번개 에너지 보고서

천둥 시는 번개로 전력을 공급받는 집들의 연결망이다. 일부 집 쌍은 전선으로 연결되어 있으며, 이 전선들은 트리를 이룬다. 즉, 임의의 두 집 사이에는 정확히 하나의 경로가 존재한다. 모든 집에는 무한한 양의 에너지를 저장할 수 있는 배터리가 있으며, 달이 시작될 때 모든 배터리의 값은 $0$이다.

한 달 동안 도시에는 번개가 여러 번 친다. 각 번개는 특이하게도 두 집을 동시에 때린다. 집 $A$는 빨간 번개를, 집 $B$는 파란 번개를 맞으며, $A$에서 $B$까지의 경로 위에 있는 모든 집(양 끝 집 포함)에 $C$만큼의 에너지를 전달한다. 이 에너지는 해당 집들의 배터리에 더해진다.

달이 끝날 때, 각 집의 배터리에 저장된 총 에너지를 보고해야 한다. 이번 달에 관측된 번개 기록을 바탕으로 정확한 보고서를 작성하라.

첫 번째 줄에는 테스트 케이스의 수 $T$ ($T \le 10$)가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

• 집의 수 $N$ ($2 \le N \le 50000$)이 한 줄에 주어진다. 집은 $0$번부터 $N-1$번까지 번호가 매겨져 있다.
• 이어지는 $N-1$개의 줄에는 각각 두 정수 $X$와 $Y$ ($0 \le X, Y \le N-1$)가 주어지며, 집 $X$와 집 $Y$가 전선으로 연결되어 있음을 뜻한다. 이 전선들은 항상 트리를 이룬다.
• 그 다음 줄에는 번개의 수 $Q$ ($1 \le Q \le 50000$)가 주어진다.
• 이어지는 $Q$개의 줄에는 각각 세 정수 $A$, $B$, $C$ ($0 \le A, B \le N-1$, $1 \le C \le 100$)가 주어진다. 이는 집 $A$에서 집 $B$까지의 경로 위 모든 집에 에너지 $C$를 더하는 번개를 뜻한다. $A$와 $B$는 같을 수도 있으며, 이 경우 그 집 하나에만 에너지가 더해진다.

각 테스트 케이스마다 먼저 Case #X: 줄을 출력한다. 여기서 $X$는 $1$부터 시작하는 테스트 케이스 번호이다. 그 다음 $N$개의 줄을 출력하는데, $i$번째 줄($i = 0, 1, \ldots, N-1$)에는 달이 끝났을 때 집 $i$의 배터리에 저장된 총 에너지를 출력한다.