닌자 택배

병우는 나뭇잎 마을의 이장이다. 나뭇잎 마을은 $N$개의 시장과 두 시장을 잇는 $N-1$개의 거리 $1$의 양방향 도로로 이루어져 있다. 임의의 서로 다른 두 시장을 도로만을 이용하여 오갈 수 있다. 즉, 나뭇잎 마을은 트리 모양이다. 편의상 각 시장에 $1$부터 $N$까지 번호를 매겨 표현하자.

최근 나뭇잎 마을은 경제 활성화로 인해 시장과 시장 사이에 물건을 옮길 필요가 많아지고 있다. 이러한 요청은 총 $Q$개로, 각 요청을 $(a, b, w)$ 라는 정수들로 표현할 수 있다. 이는 $a$번 시장에서 $b$번 시장까지 총 $w$ kg의 물건을 옮겨달라는 요청이다. 병우는 요청들을 해결하기 위해 닌자들을 고용했다. 닌자 택배를 효율적으로 활용하기 위해서는 물류 허브로 사용할 두 시장 $x$와 $y$를 잘 골라야 한다. $x$와 $y$가 서로 다를 필요는 없다.

두 시장 $a, b$에 대해, $d(a, b)$를 $a$에서 $b$로 도로만을 이용하여 갈 수 있는 최단 거리로 정의하자.

• 모든 물건은 우선 $x$번 시장으로 모여야 한다. $a$번 시장에서 $x$번 시장으로 물건을 수송하는 데는 단위 질량, 단위 거리당 $s_{a}$ 의 비용이 필요하다.
• 이후 닌자들이 신묘한 술법을 통해 $x$번 시장의 모든 물건을 $y$번 시장으로 옮긴다. 이 작업에는 단위 질량, 단위 거리 당 $u$ 의 비용이 필요하다.
• 이후 $y$번 시장에서 각 요청의 도착점으로 물건을 수송한다. $b$번 시장으로 물건을 수송하는 데는 단위 질량, 단위 거리 당 $t_{b}$의 비용이 필요하다.

즉, $a$번 시장에서 $b$번 시장으로 $w$ kg의 물건을 옮기기 위해서는 $w(s_{a}d(a, x) + u d(x, y) + t_{b}d(y, b))$의 비용이 필요함을 알 수 있다. 시장 $x, y$를 적절히 골라, 모든 $Q$개의 요청에 대한 비용의 합을 최소화하는 프로그램을 작성하여라.

첫째 줄에 나뭇잎 마을에 존재하는 시장의 개수 $N$이 주어진다.

둘째 줄부터 $N-1$개의 줄에 걸쳐 트리의 간선에 해당하는 도로에 대한 정보가 주어진다. $i+1$번째 줄에는 두 정수 $u$ $v$가 공백을 사이에 두고 주어지며, 이는 $i+1$번째 도로가 $u$번 시장과 $v$번 시장을 잇는다는 뜻이다. $1 \le u \neq v \le N$이며, 나뭇잎 마을은 트리 모양임이 보장된다.

$N+1$번째 줄부터 $N$개의 줄에 걸쳐 두 정수 $s_{i}, t_{i}$가 공백을 사이에 두고 주어진다. $s_{i}$는 $i$번 시장에서 $x$번 시장까지 1kg의 물건을 옮기는 데 드는 단위 거리당 비용, $t_{i}$는 $y$번 시장에서 $i$번 시장까지 1kg의 물건을 옮기는 데 드는 단위 거리당 비용을 나타낸다.

$2N+1$번째 줄에는 물건 수송 요청의 개수 $Q$가 주어진다.

$2N+2$번째 줄부터 $Q$개의 줄에 걸쳐 세 정수 $a, b, w$가 공백을 사이에 두고 주어진다. 이는 $a$번 시장에서 $b$번 시장까지 $w$kg의 물건을 옮겨달라는 요청이 있음을 의미한다. $a, b$는 서로 같을 수 있고, 동일한 $(a, b)$에 대해 여러 요청이 주어질 수 있음에 주의하자.

마지막 줄에는 $x$번 시장에서 $y$번 시장까지 1kg의 물건을 옮기기 위한 단위 거리당 비용 $u$가 주어진다.

첫째 줄에 $Q$개의 요청에 대한 비용의 합으로 가능한 최솟값을 출력한다.

• $1 \le N \le 100\,000$
• $1 \le Q \le 100\,000$
• $0 \le s_{i}, t_{i} \le 10^{6}$ $(1\le i \le N)$
• $0 \le u \le 10^{6}$
• 모든 $Q$개의 요청 $(a, b, w)$에 대해, $1 \le w \le 10$.