You are overseeing a game of Hot and Cold on an unweighted bidirectional tree with ~N~ nodes (numbered ~1~ to ~N~). In this game, you are the leader and there are ~S~ seekers, each playing their own individual game. This means that the game of one seeker does not impact the game of any other.

Each seeker and their game is characterized by three integers, ~a_s~, ~b_s~ and ~t_s~. The target node, ~t_s~, is the node that they are trying to find. The seeker will then traverse each node on the straight path from ~a_s~ to ~b_s~ and ask Hot or Cold? at each one. You will respond with a number, the distance from that node to the target.

After answering all these questions, you want to know the sum of answers to each node. If no question has been asked about the node, then the answer is ~0~.

Input Specification

The first line contains two integers, ~N~ ~S~.

The next ~N-1~ lines contain two integers, ~x~ ~y~, denoting an edge exists between ~x~ and ~y~.

The next ~S~ lines contain three integers, ~a_s~ ~b_s~ ~t_s~.

Constraints

~1 \le N, S \le 10^5~

~1 \le a_s, b_s, t_s \le N~

There are ~4~ subtasks worth ~\{15\%, 15\%, 35\%, 35\%\}~.

Subtask 1 & 2 [15% + 15% = 30%]

~1 \le N, S \le 100~

Subtask 1 & 3 [15% + 35% = 50%]

The target ~t_n~ is always 1 (~t_n = 1, n \in \mathbb N~)

Output Specification

Print ~N~ integers. The ~n^\text{th}~ integer being the sum of answers to queries about node ~n~. Note that answers may not fit in a 32-bit signed int.

Sample Input 1

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

Sample Output 1

0 3 2 4 2

Explanation for Sample Output 1

Sample Input 2 (not in pretests)

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

Sample Output 2

1 3 0 1 3 0