택시 여행

IOI 나라는 $N$개의 도시와 도시들을 잇는 $N - 1$개의 양방향 도로로 이루어져 있으며, 임의의 서로 다른 두 도시를 도로만 사용하여 오갈 수 있다. 즉, IOI 나라의 도로망은 트리 구조를 이룬다.

도시에는 각각 $0$ 이상 $N - 1$ 이하의 서로 다른 번호가 붙어 있으며, $0$번 도시가 IOI 나라의 수도이다. 모든 $0 \le i \le N - 2$에 대해 $i$번 도로는 $U[i]$번 도시와 $V[i]$번 도시를 잇고, 길이는 $W[i]$ km이다.

IOI 나라에서는 도시마다 택시 운임이 다르다. 모든 $0 \le i \le N - 1$에 대해 $i$번 도시에서 출발하는 택시는 기본 요금 $A[i]$원과 거리당 요금 $B[i]$원을 가진다. $i$번 도시에서 택시를 타고 $d$ km를 이동하면 $A[i] + d \times B[i]$원을 내야 한다.

서현이는 현재 수도인 0번 도시에 살고 있다. 서현이는 다른 도시들로 택시를 타고 여행을 떠나려고 한다. 서현이가 어떤 도시에 도착하면, 타고 있던 택시를 계속 타거나 그 도시에서 출발하는 택시로 갈아탈 수 있다. 택시를 갈아타면 기본 요금을 내야 하며, 거리당 요금도 바뀔 수 있다. 0번 도시에서 출발하여 다른 모든 도시로 가는 데 필요한 최소 비용을 각각 구하여라.

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