Pigtail Virus

Nana, a stage girl who travels often, discovers the land of Galrae one day. Galrae has $N$ cities, and a two-way road connects the $i$-th city ($2 \leq i \leq N$) with the $\left \lfloor \frac{i}{2} \right \rfloor$-th city. There is a positive integer $k$ that satisfies $N = 2^k - 1$. In other words, the roads of Galrae form a perfect binary tree.

No one in Galrae wears pigtails. Shocked by this, Nana sets aside her stage duties and builds $Q$ kinds of pigtail viruses.

Each virus has a power $p$ and an infectivity $d$. A virus released in city $v$ infects every city within distance $d$ of $v$, and each of those cities gains $p$. The distance between cities $a$ and $b$ is the minimum number of roads on a path from $a$ to $b$.

The infection level of a city is the sum of the powers of all viruses that infect it after Nana releases every virus. A city can be infected by two or more kinds of viruses.

Print the infection level of each city after all viruses are released.

The first line contains $N$ ($1 \leq N < 262\,144 = 2^{18}$) and $Q$ ($1 \leq Q \leq 200\,000$), separated by a space.

Each of the next $Q$ lines contains $v$, $p$, and $d$: a virus with power $p$ ($1 \leq p \leq 1\,000$) and infectivity $d$ ($0 \leq d \leq (\log_2 (N + 1) - 1) \times 2$) is released in city $v$ ($1 \leq v \leq N$).

Print $N$ integers, the infection level of each city in order, separated by spaces.