You are given a tree with $n$ vertices and $n - 1$ edges. The degree of each vertex is at most $k$.

There are $m$ undirected simple paths; the $i$-th path starts at vertex $a_i$, ends at vertex $b_i$, and carries a weight of $w_i$. We say an edge $e$ is covered by a path $(x,y)$ if and only if vertices $x$ and $y$ are disconnected when we remove edge $e$.

Please find a subset $S$ of these paths such that each edge is covered by $S$ at most once. Your goal is to maximize $\sum_{i\in S} w_i$.

Input

The first line of the input contains three integers $n,m,k$ ($2 \le n \le 10^5$, $0 \le m \le 5 \times 10^5$, $1 \le k \le 12$).

The next $n - 1$ lines, each line contains two integers $x,y$ ($1 \le x,y \le n$), denoting there is an edge connecting vertex $x$ and $y$ in the given tree.

The $i$-th of the next $m$ lines contains three integers $a_i,b_i,w_i$ ($1 \le a_i,b_i \le n$, $0 \le w_i \le 10^9$, $a_i \ne b_i$).

Output

Output a single line contains a single integer, indicating the answer.

Examples

Input 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

Output 1

19