Se te da un árbol con $n$ vértices y $n - 1$ aristas. El grado de cada vértice es como máximo $k$.

Hay $m$ caminos simples no dirigidos; el $i$-ésimo comienza en el vértice $a_i$, termina en el vértice $b_i$ y tiene un peso $w_i$. Decimos que una arista $e$ está cubierta por un camino $(x,y)$ si y solo si los vértices $x$ e $y$ quedan desconectados al eliminar la arista $e$.

Encuentra un subconjunto $S$ de estos caminos de modo que cada arista esté cubierta por $S$ como máximo una vez. Tu objetivo es maximizar $\sum_{i\in S} w_i$.

Entrada

La primera línea de la entrada contiene tres enteros $n,m,k$ ($2 \le n \le 10^5$, $0 \le m \le 5 \times 10^5$, $1 \le k \le 12$).

Cada una de las siguientes $n - 1$ líneas contiene dos enteros $x,y$ ($1 \le x,y \le n$), que indican que en el árbol dado hay una arista que conecta los vértices $x$ e $y$.

La $i$-ésima de las siguientes $m$ líneas contiene tres enteros $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$).

Salida

Imprime una línea con un único entero que indique la respuesta.

Ejemplos

Entrada 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

Salida 1

19