특이한 함정

악당 리들러가 고담시 주민들을 노리는 새로운 함정을 설계했다. 함정은 $n$개의 방과 방들을 잇는 통로로 이루어지며, 임의의 방 $u$에서 다른 방 $v$로 가는 경로는 하나뿐이다.

방 사이를 이동하려면 함정의 모든 통로를 지날 수 있는 특수 엘리베이터를 써야 한다. 엘리베이터에는 한 번에 최대 $b$명까지 탈 수 있다. 엘리베이터가 사람을 한 명이라도 태운 채 방 $u_i$에서 방 $v_i$로 이동하면 내구도가 $w_i$만큼 줄어든다. 이동하는 동안 아무도 타지 않았다면 내구도는 줄지 않는다.

리들러는 사람들을 $m$개의 그룹으로 나눈다. 그룹 $i$에는 방 $x_i$에서 출발해 방 $y_i$로 가야 하는 $c_i$명이 있다. 사람들은 이동 중 어느 곳에서든 잠시 내렸다가 기다린 뒤 다시 탈 수 있다.

악당은 엘리베이터가 모든 사람을 목적지에 데려다 준 직후 내구도가 정확히 $0$이 되어 무너지기를 원한다. 사람들을 옮기는 동안 엘리베이터가 입을 수 있는 최소 피해를 구하라.

첫 줄에 공백으로 구분된 정수 $n$, $m$, $b$가 주어진다 ($2 \le n \le 10^5$; $1 \le m \le 2 \cdot 10^5$; $1 \le b \le 10^9$).

다음 $n - 1$개 줄은 통로를 설명한다. $i$번째 줄의 세 정수 $u_i$, $v_i$, $w_i$는 방 $u_i$와 $v_i$ 사이에 통로가 있고, 사람을 한 명이라도 태우고 지나면 엘리베이터가 $w_i$만큼 피해를 입는다는 뜻이다 ($1 \le u_i, v_i \le n$; $0 \le w_i \le 10^4$). 어느 방에서든 다른 모든 방으로 통로를 따라 갈 수 있다는 것이 보장된다.

다음 $m$개 줄은 사람 그룹을 설명한다. $i$번째 줄의 세 정수 $x_i$, $y_i$, $c_i$는 출발 방, 도착 방, 그룹의 인원 수이다 ($1 \le x_i, y_i \le n$; $1 \le c_i \le 10^9$).

모든 사람이 탈출한 뒤 엘리베이터가 입는 내구도 피해의 최솟값을 정수 하나로 출력한다.

첫 번째 예제에서 방들은 $2 \leftrightarrow 3 \leftrightarrow 4 \leftrightarrow 1$ 순서로 일렬로 이어져 있다. 가능한 이동 순서는 다음과 같다.

1. 2번 방의 5명을 4번 방으로 데려간다 (내구도 3 감소).
2. 2번 방으로 돌아가 2명을 태운다. 4번 방으로 가는 길에 3번 방에서 3명을 더 태운다 (내구도 3 감소).
3. 1번 방까지 간 뒤 1번 방의 5명을 2번 방으로 옮긴다 (내구도 5 감소). 돌아오는 길에 3번 방의 5명을 4번 방으로 옮긴다 (내구도 감소 없음).
4. 남은 4명에 대해 마지막 단계를 반복한다 (내구도 5 감소).

두 번째 예제에서 최적 방법 중 하나는 먼저 모든 사람을 3번 방까지 옮기는 것이다. 이때 2번 방에서 출발한 사람들은 1번 방에서 동행을 태워야 한다. 그다음 사람들을 가능한 가장 큰 묶음으로 나누어 각자의 목적지로 옮긴다.