27406번 - 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₀, C₁, …, C_L he couldn't resist calculating the sum of those even-indexed S = C₀ + C₂ + C₄ + … + C_2K + … . 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.

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.

The input 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.

The ouptut 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.

• 1 ≤ N ≤ 200,000
• 1 ≤ M ≤ 200,000
• 1 ≤ no_i ≤ M for all 1 ≤ i ≤ M
• It is guaranteed that all stations are reachable from each other

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