Metro

In recent years the Compulsive Disorder Research Institute became increasingly busy with discovering and classifying all sorts of peculiar behaviors. You have been dispatched to investigate one such strange compulsion reported amongst the innocent everyday metro travelers.

The underground metro consists of $N$ stations connected by $N-1$ bidirectional paths and $M$ metros with linear routes, each having a unique number. The issue concerns the displays located within the stations that show the numbers of the metros passing through their respective station in sorted order. One of your subjects proclaimed that whenever he saw a list of integers $C_0, C_1, \dots, C_L$ he couldn't resist calculating the sum of those even-indexed $S = C_0 + C_2 + C_4 + \dots + C_{2K} + \cdots$. One such list can be seen on each of the displays located inside the metro stations.

Before any assumptions can be made about those afflicted, the sum for each of the $N$ displays needs to be calculated. Unfortunately if you manually count those numbers there is a definite chance you might actually end up suffering from this specific disorder. As such you are to write a program that computes them for you, thus protecting your mind from potential insanity.

Task

Given the number of stations, $N$, the way in which they are connected, as well as the $M$ metros, compute the necessary sum for each of the $N$ stations.

Input data

The file metro.in contains two integers on the first line, $N$ and $M$. The following $N-1$ lines each contain two integers $x_i$, $y_i$ meaning there is a direct link between stations $x_i$ and $y_i$.

The next $M$ lines describe the metros using three integers $a_i$, $b_i$ and $no_i$ meaning that the route of the metro numbered $no_i$ goes from station $a_i$ to station $b_i$.

Output data

The file metro.out must contain $N$ lines. Line $i$ must contain a single number, the sum for the display in the station with number $i$. If there are no trains at all passing through station $i$, write the number $0$ on line $i$.

Constraints and clarifications

• $1 \leq N \leq 200 \ 000$
• $1 \leq M \leq 200 \ 000$
• $1 \leq no_i \leq M$ for all $1 \leq i \leq M$
• It is guaranteed that all stations are reachable from each other.

Example

metro.in

6 4
1 2
2 4
2 6
1 3
5 2
5 6 3
4 5 1
4 3 2
1 2 4

metro.out

2
4
2
1
1
3

Explanation

The displays are showing the following numbers:

Station $1$: $2, 4$
Station $2$: $1, 2, 3, 4$
Station $3$: $2$
Station $4$: $1, 2$
Station $5$: $1, 3$
Station $6$: $3$