You are given a tree of $n$ vertices rooted at $1$. Each vertex has a number, initially $0$.
There are $q$ queries, each of the form $(u, v, w)$, increasing each vertex on the simple path between $u$ and $v$ by $w$.
Find the value on each vertex after $q$ queries.
### Input
- The first line contain 2 integers $n, q$.
- The next $n - 1$ lines, each line contains 2 integers $u, v$, there is an edge between $u$ and $v$.
- The next $q$ lines, each line contains 3 integers $u, v, w$, an query.
### Output
- Print $n$ integers, the $i^{th}$ number is the value on vertex $i$.
### Constraints
- $1 \le n, q\le 10^5$.
- $1 \le u, v \le n$.
- $1 \le w \le 10^9$.
### Example
Input:
```
7 3
1 2
1 3
2 4
2 5
3 6
3 7
1 4 1
5 6 2
6 7 5
```
Output:
```
3 3 7 1 2 7 5
```
