$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 \ne 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