[AdditionalFile6779.zip](file://AdditionalFile6779.zip?type=additional_file)

#6779. 「2021 营员交流」奖励游戏

标签: 传统 | 时间限制: 4000 ms | 内存限制: 512 MiB |

题目描述

daklqw 在玩一个奖励游戏。

这个游戏在一棵有 $n$ 个节点的树上面进行，一共有 $t$ 秒，你一开始在 $s$ 点。

显然，这棵树一共有 $n - 1$ 条边，这 $n - 1$ 条边中，有一些是奖励边，也有一些是普通边，对于边 $(u, v)$，如果其为奖励边，你从 $u$ 到 $v$ 或者 $v$ 到 $u$ 均可以获得奖励。普通边啥也没有。

在每一秒，你最多通过一条边，当然你也可以不动。

每次奖励是获得额外的 $c$ 积分。

当然如果仅仅是这样，这个游戏就没有意思了，你还可以做一些任务，在 节点 $D$，第 $A$ 秒 开始，持续 $K$ 秒，完成之后可以获得 $p$ 积分。

需要注意的是：每个任务只能做一次，做任务的时候不可以离开这一个节点，在同一时刻只能做一个任务。

需要额外注意的是：存在持续 $0$ 秒的任务，这个任务只需该时刻在对应的点即可完成，也就是说可以同时完成多个这样的任务，并且不需要停留。

daklqw 想要知道，他在每一个节点开始，最多获得多少积分。

你可以帮帮 dak 吗？

输入格式

第一行四个正整数 $n, q, t, c$，表示树上的节点数，任务数，游戏时间，奖励积分数。

下面 $n - 1$ 行，每行三个正整数 $x_i, y_i, o_i$，表示 $x_i$ 到 $y_i$ 有一条边，$o_i$ 是这条边的类型，若 $o_i = 0$，那么他是一条普通边，若 $o_i = 1$，那么他是一条奖励边。

下面 $q$ 行，每行三个正整数 $D_i, A_i, K_i, p_i$，表示任务的所在节点，开始时间，持续时间，奖励积分数。

输出格式

一行 $n$ 个正整数，第 $i$ 个表示在节点 $i$ 开始时，最多获得的奖励积分。

样例

输入

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

输出

8 7 7 7 6

数据范围与提示

对于所有数据 $1 \leq n, q \leq 10^5, 0\leq A_i \leq A_i + K_i \leq t \leq 10^8$。

$1 \leq c, p_i \leq 10^8$。

$0 \leq o_i \leq 1$

$1 \leq x_i, y_i, D_i \leq n$。

$\text{Subtask 1（10 pts）}$：保证 $1\leq n, t \leq 10$。

$\text{Subtask 2（20 pts）}$：保证 $1\leq n, q, t \leq 1000$。

$\text{Subtask 4（15 pts）}$：保证 $1\leq n, q \leq 1000$。

$\text{Subtask 5（20 pts）}$：保证 $1\leq n, q \leq 30000$。

$\text{Subtask 5（15 pts）}$：保证 $1\leq n, q \leq 60000$。

$\text{Subtask 6（20 pts）}$：没有特殊限制。