给定一棵有 $n$ 个顶点和 $n-1$ 条边的树。每个顶点的度数最多为 $k$。

现有 $m$ 条无向简单路径；第 $i$ 条路径的起点为 $a_i$，终点为 $b_i$，权重为 $w_i$。当且仅当删除边 $e$ 后顶点 $x$ 和 $y$ 不连通时，我们称边 $e$ 被路径 $(x, y)$ 覆盖。

请找出一个路径子集 $S$，使得每条边被 $S$ 中的路径覆盖次数不超过一次。你的目标是最大化 $\sum_{i \in S} w_i$。

输入格式

第一行包含三个整数 $n, m, k$ ($2 \le n \le 10^5, 0 \le m \le 5 \times 10^5, 1 \le k \le 12$)。

接下来的 $n-1$ 行，每行包含两个整数 $x, y$ ($1 \le x, y \le n$)，表示给定树中连接顶点 $x$ 和 $y$ 的一条边。

接下来的 $m$ 行中，第 $i$ 行包含三个整数 $a_i, b_i, w_i$ ($1 \le a_i, b_i \le n, 0 \le w_i \le 10^9, a_i \neq b_i$)。

输出格式

输出一行，包含一个整数，表示答案。

样例

样例输入 1

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

样例输出 1

19