题目描述

给定一棵 n 个节点的树，节点编号 1∼n，根节点为 1。有 m 次操作，每次操作给定 u,v,k，表示将路径 u→v 上的所有节点权值加 k。最后输出每个节点的最终权值。

输入格式

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

输出格式

一行 n 个整数，分别表示节点 1∼n 的最终权值

样例输入

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

样例输出

3 3 2 1 2