题目描述

小 X 有一颗 $n$ 个结点的树，树的根结点为 $1$，规定根结点的深度为 $1$。树是指一个由 $n$ 个结点，$n-1$ 条双向边组成的连通块。你通过每条边都需要 $1$ 秒。你在每秒钟可以停在原地，也可以经过 $1$ 条边。

树的结点会随机刷新 $m$ 次，第 $i$ 次在 $t_i$ 时刻在 $w_i$ 号结点刷新出 $p_i$ 个苹果，但存在时间只有 $1$，过后会消失。

这颗树有两个特殊的性质：

• 最深的结点深度不会超过 $s$。

• 所有的 $t_i$ 均不相同。

最开始时，你在根结点，请问你最多能采多少个苹果。

输入格式

第一行 $n,m,s$。

后面 $n-1$ 行，每行两个数，$u_i,v_i$，代表，描述树的一条边。

后面 $m$ 行，每行三个数，$w_i,t_i,p_i$ 代表 $t_i$ 时刻在 $w_i$ 刷新 $p_i$ 个苹果。

输出格式

输出一个数，代表最多能摘到的苹果个数。

5 3 5
1 2
1 3
2 4
2 5
1 5 3
2 7 8
3 8 10

13

提示

本题采用捆绑测试。 | 子任务编号 | $n$ | $m$ | 特殊性质 | 分值| | :----------: | :----------: | :----------: | :----------: | :----------: | | $1$ | $= 5$ | $= 5$ |无 |$10$| | $2$ | $= 20$ | $= 20$ | 无 |$10$| | $3$ | 无 | 无 | A |$20$| | $4$ | 无 | 无 | B |$20$| | $5$| $= 10^3$ | $= 10^3$ | 无 |$20$| | $6$| 无 | 无 | 无 |$20$|

对于 $100\%$ 的数据，$1 \le n \le 8 \times 10^4,1 \le m \le 2 \times 10^4,1 \le s \le 10^3,1 \le p_i,t_i \le 10^9,1 \le w_i \le n$。

特殊性质 A：$s = 2$。

特殊性质 B：这棵树是一条以根节点为端点的链。