Taxi Trip

The IOI country has $N$ cities and $N - 1$ bidirectional roads connecting them, and any two different cities can be reached from each other using only roads. In other words, the road network of the IOI country forms a tree.

Each city has a distinct number from $0$ to $N - 1$, and city $0$ is the capital of the IOI country. For every $0 \le i \le N - 2$, road $i$ connects city $U[i]$ and city $V[i]$, and its length is $W[i]$ km.

Taxi fares differ by city. For every $0 \le i \le N - 1$, a taxi departing from city $i$ has a base fare of $A[i]$ won and a per-kilometer fare of $B[i]$ won. If you ride a taxi from city $i$ for $d$ km, you pay $A[i] + d \times B[i]$ won.

Seohyun lives in city 0, the capital. She wants to travel to other cities by taxi. When she arrives at a city, she can keep riding her current taxi or switch to a taxi departing from that city. Switching taxis requires paying the base fare again, and the per-kilometer fare may change. For each city, compute the minimum cost to travel from city 0 to that city.

• $2 \le N \le 100\,000$
• For all $i$, $0 \le A[i] \le 10^{12}$ ($0 \le i \le N - 1$)
• For all $i$, $0 \le B[i] \le 1\,000\,000$ ($0 \le i \le N - 1$)
• For all $i$, $0 \le U[i], V[i] \le N - 1$; $U[i] \ne V[i]$ ($0 \le i \le N - 2$)
• For all $i$, $1 \le W[i] \le 1\,000\,000$ ($0 \le i \le N - 2$)