题目描述

给定一棵$n$个节点的无根树，节点编号$1 \sim n$，根节点为1。 有$m$次操作，每次操作给定$u, v, k$，表示将路径$u \to v$上的所有边的权值加$k$。 初始时所有边的权值为0，操作完成后，输出每个节点对应边的最终权值（即节点$u$对应父→$u$的边，根节点1无对应边，输出0）。

输入格式

• 第一行：两个整数$n, m$（$1 \le n, m \le 10^5$）；
• 接下来$n-1$行：每行两个整数$u, v$，表示树的一条无向边；
• 接下来$m$行：每行三个整数$u, v, k$，表示一次路径边权加操作。

输出格式

一行$n$个整数，依次表示节点$1 \sim n$对应边的最终权值（节点1输出0）。

样例输入

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

样例输出

0 1 2 1 2