$n$ 個の頂点と $n - 1$ 本の辺からなる木が与えられます。各頂点の次数は高々 $k$ です。

$m$ 本の無向単純パスがあります。$i$ 番目のパスは頂点 $a_i$ から始まり、頂点 $b_i$ で終わり、重み $w_i$ を持ちます。辺 $e$ を取り除くと頂点 $x$ と $y$ が連結でなくなる場合、かつその場合に限り、辺 $e$ はパス $(x,y)$ によって覆われるといいます。

各辺が $S$ によって高々 1 回覆われるような、これらのパスの部分集合 $S$ を求めてください。目標は $\sum_{i\in S} w_i$ を最大化することです。

入力

入力の最初の行には 3 つの整数 $n,m,k$ ($2 \le n \le 10^5$, $0 \le m \le 5 \times 10^5$, $1 \le k \le 12$) が含まれます。

続く $n - 1$ 行にはそれぞれ 2 つの整数 $x,y$ ($1 \le x,y \le n$) が含まれ、与えられた木に頂点 $x$ と $y$ を結ぶ辺があることを表します。

続く $m$ 行のうち $i$ 行目には 3 つの整数 $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$) が含まれます。

出力

答えを表す整数を 1 行に出力してください。

入出力例

入力 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