Ninja Delivery

Byeongwoo is the village head of Leaf village. Leaf village has $N$ markets and $N-1$ bidirectional roads of length $1$ that connect pairs of markets. Any two different markets can reach each other using only roads. In other words, Leaf village is shaped like a tree. For convenience, the markets are numbered from $1$ to $N$.

Recently, the economy of Leaf village has grown, so goods need to be moved between markets more often. There are $Q$ such requests. Each request is written as three integers $(a, b, w)$, meaning that $w$ kg of goods must be moved from market $a$ to market $b$. Byeongwoo hired ninjas to handle the requests. To use the ninja parcel service efficiently, he must choose two markets $x$ and $y$ to serve as logistics hubs. $x$ and $y$ do not need to be different.

For two markets $a$ and $b$, let $d(a, b)$ be the shortest distance from $a$ to $b$ when traveling only along roads.

• All goods must first be gathered at market $x$. Moving goods from market $a$ to market $x$ costs $s_{a}$ per kilogram per unit distance.
• Then the ninjas use a mysterious technique to move all goods at market $x$ to market $y$. This costs $u$ per kilogram per unit distance.
• Finally, goods are carried from market $y$ to the destination of each request. Moving goods to market $b$ costs $t_{b}$ per kilogram per unit distance.

In other words, moving $w$ kg of goods from market $a$ to market $b$ costs $w(s_{a}d(a, x) + u d(x, y) + t_{b}d(y, b))$. Choose the markets $x$ and $y$ so that the total cost of all $Q$ requests is minimized, and write a program that finds this minimum.

The first line contains the number of markets $N$.

Each of the next $N-1$ lines contains two integers $u$ and $v$, separated by a space. This means that the $i+1$-th road connects market $u$ and market $v$. It is guaranteed that $1 \le u \neq v \le N$ and that the roads form a tree.

Each of the next $N$ lines contains two integers $s_{i}$ and $t_{i}$, separated by a space. $s_{i}$ is the cost per unit distance per kilogram of moving goods from market $i$ to market $x$. $t_{i}$ is the cost per unit distance per kilogram of moving goods from market $y$ to market $i$.

The line after that contains the number of requests $Q$.

Each of the next $Q$ lines contains three integers $a$, $b$, and $w$, separated by spaces. This means that $w$ kg of goods must be moved from market $a$ to market $b$. $a$ and $b$ may be equal, and the same $(a, b)$ pair may appear in more than one request.

The last line contains $u$, the cost per unit distance per kilogram of moving goods from market $x$ to market $y$.

Print the minimum possible total cost of all $Q$ requests on the first line.

• $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}$
• For all $Q$ requests $(a, b, w)$, $1 \le w \le 10$.