닌자 택배

병우는 나뭇잎 마을의 이장이다. 나뭇잎 마을은 $N$개의 시장과, 두 시장을 잇는 길이 $1$인 양방향 도로 $N-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$번 시장까지 1 kg의 물건을 옮기는 데 드는 단위 거리당 비용이고, $t_{i}$는 $y$번 시장에서 $i$번 시장까지 1 kg의 물건을 옮기는 데 드는 단위 거리당 비용이다.

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

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

마지막 줄에는 $x$번 시장에서 $y$번 시장까지 1 kg의 물건을 옮기는 단위 거리당 비용 $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$.