题目描述

给定一棵大小为 $n$ 的树。树上节点编号从 $1$ 到 $n$。

树上有 $n-1$ 条边，其中第 $i$ 条边表示为三个整数 $u_i, v_i, w_i$，其中 $u_i$ 和 $v_i$ 表示第 $i$ 条边连接的两个节点的编号，$w_i$ 表示第 $i$ 条边初始的权值。

接下来有 $m$ 次操作。其中第 $i$ 次操作表示为三个整数 $x_i, y_i, z_i$，它表示你需要将以节点 $u_i$ 为起点，节点 $v_i$ 为终点的简单路径上的每一条边的权值都增加 $z_i$。

请你输出 $m$ 次操作结束后，树上每条边的权值。

输入格式

第一行，一个整数 $n(2 \le n \le 2 \times 10^5)$，表示树的大小。

接下来 $n-1$ 行，每行包含三个整数 $u_i, v_i, w_i$，表示树上一条边的信息（$1 \le u_i, v_i \le n, -1000 \le w_i \le 1000$）。

接下来一行，一个整数 $m(1 \le m \le 2 \times 10^5)$，表示操作次数。

接下来 $m$ 行，每行包含三个整数 $x_i , y_i, z_i$，表示一次操作（$1 \le x_i, y_i \le n, -1000 \le w_i \le 1000$）。

输出格式

输出共一行，包含 $n-1$ 个整数，两两之间以一个空格分隔。其中第 $i$ 个整数表示最终第 $i$ 条边的权值。

样例

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

5 3 8 6 8

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$n,m \le 20$
• 对于 $60\%$ 的数据，$n,m \le 2000$
• 对于 $100\%$ 的数据，$1 \le n,m \le 2 \times 10^5$