Maximizing Trade Profit on a Tree

On the continent of EJOI there are (N) cities numbered from (1) to (N), connected by (N-1) bidirectional roads forming a tree. In addition, there are (K) trade relations. Each trade relation is described by a pair of cities ((A,B)) and a profit (C).

The king will first choose a city (H) as the capital, and the tree is then rooted at (H). The prince is then allowed to select at most two cities that are adjacent to (H). Once a neighbor is chosen, the prince gains control over the entire subtree rooted at that neighbor (when (H) is taken as the root), in addition to the capital (H) itself. The profit the prince obtains is the sum of the profits of all trade relations such that both endpoints are under his control. Note that a trade relation will contribute its profit if and only if both cities involved are in the controlled set.

For each city (H) (from (1) to (N)) taken as capital, determine the maximum profit the prince can obtain by optimally selecting at most two of (H)'s adjacent cities.

inputFormat

The first line contains two integers (N) and (K) denoting the number of cities and the number of trade relations, respectively.
The next (N-1) lines each contain two integers (u) and (v), describing a bidirectional road between cities (u) and (v).
The following (K) lines each contain three integers (A), (B) and (C), indicating that there is a trade relation between cities (A) and (B) with profit (C).
(1 \le u, v, A, B \le N).

outputFormat

Output (N) integers in one line separated by spaces. The (i)-th integer should be the maximum profit the prince can achieve when city (i) is chosen as the capital.

sample

3 2
1 2
2 3
1 2 10
2 3 5

15 15 15